>> [MUZIKO Ludante]
>> ANDI PENG: Bonvenon semajno 6 de sekcio.
Ni deviis de nia normo sekcio tempo de mardo
posttagmezo al tiu bela dimanĉa mateno.
Dankon por ĉiuj kiuj aliĝis al mi hodiaŭ, sed serioze,
ĉirkaŭvojon de aplaŭdoj.
>> Tio estas sufiĉe granda peno.
Mi preskaŭ ne eĉ fari en tempo, sed estis okej.
Do mi scias ke vi ĉiuj ĵus faris ĝin al la kvizo.
Unue, bonvenon al la flip flanko de tio.
>> Due, ni parolos pri tio.
Ni parolos pri la kvizo.
Ni parolos pri kiom vi faras en la klaso.
Vi estos bone.
Mi havas viajn kvizojn por vi fine de tie,
do se vi infanoj volas preni oni rigardas ĝin, tute bone.
>> Tiel rapide ol ni komencos, la tagordo por hodiaŭ estas kiel sekvas.
Kiel vi povas vidi, ni estas esence rapidan pafon
tra tuta fasko de datumstrukturoj vere, vere, vere rapide.
Do kiel tia, ĝi ne estos súper interaga hodiaŭ.
Ĝi devos simple esti mi specon de bruo aferojn vi, kaj se mi konfuzas vin,
se mi iras tro rapide, sciigu min.
Ili estas nur diversaj datumoj strukturoj, kaj kiel parto
de via pset por tiu venonta semajno, vi
esti demandita apliki unu el ili, eble du el them-- ambaux
en via pset.
Bone, do mi simple tuj starti kun iuj anoncoj.
Ni transiru stakoj kaj atendovicoj pli en profundo ol kion ni faris antaŭe la kvizo.
Ni transiru ligitaj listo denove, refoje,
pli ĝisfunde ol kio ni havis antaŭ la kvizo.
Kaj tiam ni parolos pri hash tabloj, arboj kaj provas, kion
estas ĉiuj belaj necesa por via pset.
Kaj tiam ni iros super kelkaj helpema konsiloj por pset5.
>> Bone, do kvizo 0.
La mezumo estis de 58%.
Ĝi estis tre malalta, kaj tiel vi infanoj ĉiuj faris tre, tre bone en konsento
kun tio.
>> Pli malpli, regulo de thumb estas se vi estas ene norma devio de la meznombro
Precipe pro ni estas en malpli comfy sekcio, vi tute bone.
Vi estas sur trako.
Vivo estas bona.
>> Mi scias ke estas timiga pensi ke Mi akiris kiel 40% sur tiu kvizo.
Mi tuj malsukcesos tiu klaso.
Mi promesas al vi, ke vi ne estas tuj malsukcesos la klaso.
Vi tute bone.
>> Por tiuj de vi kiu superis Dume, impresa, impona,
kiel, serioze bone farita.
Mi havas ilin kun mi.
Bonvolu veni akiri ilin fine de sekcio.
Lasu min scii se vi havas ajnan demandoj, demandojn kun ili.
Se ni aldonas vian poentaron erara, sciigu nin.
>> Bone, do pset5, tiu estas vere weird semajno por Yale en la senco
ke nia pset estas pro Merkredo tagmeze inkluzive
Fine tago, do ĝi estas reale teorie pro mardo tagmeze.
Probable neniu finis ĉe mardo tagmeze.
Tio estas tute bone.
Ni tuj devas oficejo horoj ĉinokte krom lundo nokte.
Kaj ĉiuj de la sekcioj tiu semajno reale esti igitaj metiejoj,
do bonvolu aperigi en ajna sekcio vi volas,
kaj ili estos speco de mini-pset laborejoj por helpo pri tio.
Do kiel tia, tio estas la nura sekcio kie ni instrumaterialo.
Ĉiuj aliaj sekcioj estos koncentranta ekskluzive en helpo por la pset.
Yeah?
>> Spektantaro: Kie oficejo horoj?
>> ANDI PENG: Oficejo horoj tonight-- ho, bona demando.
Mi pensas oficejo horoj ĉinokte estas en Teal aŭ ĉe Komunejo.
Se vi kontrolu rete CS50 kaj vi iros al oficejo horoj,
tie devus esti horaro kiu diras vin kie ĉiuj ili estas.
>> Mi scias ĉu ĉi-nokte aŭ morgaŭ estas Teal,
kaj mi pensas ke ni povas havi commons por kelkaj noktoj.
Mi ne certas.
Bona demando.
Kontrolu sur CS50.
>> Cool, demandojn pri la horaro por la venonta kiel tri tagoj?
Mi promesas vin uloj kiel Davido diris, ĉi tiu estas la supro de la monteto.
Vi uloj estas preskaŭ tie.
Nur tri tagojn.
Akiri tie, kaj poste ni ĉiuj venos.
Ni havos belan CS-libera paŭzo.
Ni revenos.
Ni plonĝi en retejo programado kaj disvolviĝo,
aferojn, kiuj estas tre amuza kompari al iuj el la aliaj psets.
Kaj ĝi estos malvarma, kaj ni havos multa amuza.
Ni devos pli dolĉa.
Pardonu pro dolĉaĵoj.
Mi forgesis dolĉaĵoj.
Estis malglata mateno.
Do vi infanoj estas preskaŭ tie, kaj mi estas vere fiera pri vi uloj.
>> Bone, do stakigas.
Kiu amis la demando pri Jack kaj liaj vestoj sur la kvizo?
Neniu?
Okej, tio estas bone.
>> Do esence kiel vi povas bildo Joĉjo, ĉi ulo ĉi tie,
amas preni la vesto el la supro de la pilo,
kaj li metas ĝin reen sur la pilo post li faris.
Do en tiu maniero, li neniam ŝajnas esti akiranta
al la fundo de la pilo en sia vesto.
Do tiu tipo de Priskribas la baza datumstrukturo
de kiel stako estas efektivigita.
>> Esence, elpensi pilo kiel ajna stako de objektoj
kie meti aferojn sur la supro, kaj tiam vi pop ilin de la supro.
Do LIFO estas mallongigo ni ŝatas al use-- Lasta En, Unua Out.
Kaj tiel daŭris en la supron de la pilo estas la unua kiu eliras.
Kaj do la du terminoj ni ŝatas asocii
kun tiel nomataj puŝo kaj popo.
Kiam vi puŝi ion sur la pilo, kaj vi pop ĝin reen supren.
>> Kaj do versxajne tiu estas speco de abstrakta koncepto por tiuj de vi
kiuj volas vidi kiel fakta efektivigo de tiu
en la reala mondo.
Kiel multaj el vi skribis eseon eble kiel horo antaŭ ĝi ŝuldiĝis,
kaj vi hazarde forigita grandega eron de ĝi, kiel hazarde?
Kaj tiam kion fari kontrolo ni uzas por meti ĝin reen?
Kontrolo-Z, Yeah?
Kontrolo-Z, do la kvanton de tempoj ke Kontrolo-Z savis mian vivon,
savis mian pugon, ĉiufoje ke estas implementado tra pilo.
>> Esence ĉiu informo jen sur via Word dokumento,
gets puŝis kaj krevita laŭvole.
Kaj tiel esence kiam ajn vi forigi ion, vi pop ĝin reen supren.
Kaj tiam se vi bezonas ĝin reen sur, vi puŝi ĝin, kiu estas kion Kontrolo-C faras.
Kaj tiel reala mondo funkcio de kiel simpla datumstrukturo
povas helpi kun via ĉiutaga vivo.
>> Do struct estas la vojo ni fakte krei pilo.
Ni tajpu difini struct, kaj tiam ni nomas ĝin stakigi funde.
Kaj ene de la stako, ni havos du parametroj
ke ni povas esence manipuli, do ni havos char stelo kordoj kapablo.
>> Ĉiuj ke ĝi faras kreas tabelon
ke ni povas stoki ajn vi volas kion ni povas determini lian kapablon.
Kapablo estas nur la max kvanto de erojn ni povas meti en tiun tabelo.
int grandeco estas la vendotablo kiu tenas trako de kiom da eroj estas aktuale
en la stako.
Tial do ni povu kontroli, A, ambaŭ kiom granda la fakta pilo estas,
kaj, B, kiom de tiu pilo ni plenigis ĉar ni ne volas
superflui super kio nia kapablo estas.
>> Do ekzemple, ĉi amindaj demando estis en via kvizo.
Esence kio faras nin puŝi sur la supro de stako.
Sufiĉe simpla.
Se vi rigardas ĝin, ni trairu ĉi.
Se [inaudible] size-- memoras, kiam ajn vi
deziras aliri ajnan parametro ene struct,
vi faru la nomon de la struct.parameter.
>> En tiu kazo, s estas la nomo de nia stako.
Ni volas aliri la grandeco de ĝi, do ni faru s.size.
Do tiel longe kiel la grandeco ne estas egala al kapacito aŭ kiel longe
kiel ĝi estas malpli ol kapablo, ĉu laborus tie.
>> Vi volas aliri interne de via pilo, do s.strings,
kaj vi tuj metis tiun novan numeron ke vi volas enmeti en tie.
Ni nur diras ni volas enmeti int n sur la pilo,
ni povus fari s.strings, krampoj, s.size egalas n.
Pro grandeco estas kie ni nuntempe estas en la stako
se ni tuj puŝi ĝin, ni simple aliri
kie ajn la grandeco estas, la nuna pleneco de la pilo,
kaj ni puŝi la int n sur ĝi.
Kaj poste ni volas certigi ke ni ankaŭ pliigante grandecon de la n,
tiel ni povas sekvigi ni havas aldonis ekstran aferon al la stako.
Nun ni havas pli grandan grandecon.
Ĉu ĉi tie sencon ĉiuj, kiel logike funkcias?
Estis speco de rapida.
Spektantaro: Ĉu vi povas iri super la s.stringss.strings [s.size] denove?
ANDI PENG: Certe, do kion faras s.size nuntempe al ni?
Spektantaro: Ĝi estas la aktuala grandeco.
ANDI PENG: Ekzakte, do la nuna indekso ke nia grandeco estas je,
kaj do ni volas meti la nova entjero ke ni volas enmeti en s.size.
Ĉu tio havas sencon?
Ĉar s.strings, cxiuj estas estas la nomo de la tabelo.
Ĉiuj estas estas aliranta la tabelo ene nia struct,
kaj do se ni volas meti n en tiun indekson,
ni povas simple aliri ĝin uzante krampoj s.size.
Malvarmeta.
>> Bone, popo, mi _Pseudocode_ ĝin cxar vi uloj, sed simila koncepto.
Ĉu tio havas sencon?
Se la grandeco estas pli granda ol nulo, tiam vi
scias ke vi volas preni ion ĉar se la grandeco ne estas
pli granda ol nulo, tiam vi havas nenion en la stako.
>> Do vi nur volas ekzekuti tiun kodon, ĝi povas nur
pop se estas iu krevi.
Do se la grandeco estas pli granda ol 0, ni minus la grandeco.
Ni dekremento la grandeco kaj tiam reveni kiom estas ene de ĝi pro
per krevanta, ni volas aliro ajn estas stokita
en la indekso de la supro de la stako.
Ĉio estas ebla solvo?
Se mi vin uloj skribi ĉi ekstere, volus vin uloj povos skribi gxin?
OK, vi infanoj povas ludi kun ĝi.
Neniu ĉagrenoj se vi ne ricevas ĝin.
Ni ne havas tempon por programi ĝin hodiaŭ ĉar ni jam
akiris multan tiuj strukturoj iri tra, sed esence
_pseudocode_, tre, tre simila al peli.
Nur sekvi laŭ la logiko.
Certiĝu vi konsentas ĉiuj ĉefaĵoj de via struct korekte.
Yeah?
>> Publiko: Will tiuj diapozitivoj kaj tiu tuta afero esti ĝis hodiaŭ-ish?
ANDI PENG: Ĉiam, Yep.
Mi tuj provos meti ĉi supre kiel horo post.
Mi retmesaĝi David David provos meti ĝin supre kiel horo post tio.
>> Bone, do tiam ni moviĝas en tiu alia amindaj datumstrukturo nomata vosto.
Kiel vi uloj povas vidi ĉi tie, atendovico, por la britoj inter ni,
ĉiuj estas estas linio.
Do male al kio vi pensas pilo estas,
atendovico estas ekzakte kion logike vi pensas ĝin estas.
Ĝi estas tenita fare de la reguloj de FIFO, kiu estas la unua en, Unua Out.
Se vi estas la unua unu en la vico, vi estas
la unua kiu venas el la linio.
>> Do kion ni ŝatas nomi tiun estas dequeueing kaj enqueueing.
Se ni volas aldoni ion al nia vosto, ni enqueue.
Se ni volas dequeue, aŭ preni io for, ni dequeue.
>> Do sama senco ke ni estas speco de kreanta fiksa grandeco elementoj kiujn ni
povas stoki iujn aferoj, sed ni ankaŭ povas
ŝanĝi kie ni metante parametroj ene de ili
bazita sur kio tipo de funcionalidad ni volas.
Do stakoj, ni volis la lasta unu, N al esti la unua unu eksteren.
Atendovico estas ni volas la unua aĵo en esti la unua afero ekstere.
>> Do la struct-tipo difini, kiel vi povas vidi,
ĝi estas iomete malsama el kio la stako estis
ĉar ne nur ni devas teni trako de kie la grandeco aktuale estas,
ni ankaŭ volas konservi trako de la kapo krom kie ni nune estas.
Do mi pensas, ke estas pli facile se mi tiros ĉi supre.
Do imagu ni hvas atendovico, tiel diru la estro estas ĉi tie.
La kapo de la linio, ni nur diru ke estas aktuale tie,
kaj ni volas enmeti io en la vico.
Mi tuj vokos grandeco esence Estas la sama afero kiel vosto,
Fine de kien viaj atendovico estas.
Ni nur diras grandeco pravas tie.
>> Do kiel faras unu feasibly enmeti ion en atendovico?
Kio indekso ni volas meti kie ni volas enmeti en.
Se ĉi tiu estas la komenco de via vosto kaj ĉi tiu estas la fino de ĝi
aŭ la grandeco de ĝi, kie ni volas aldoni la sekvantan objekton?
>> Spektantaro: [inaudible]
ANDI PENG: Precize, vi volas aldoni ĝi depende vi skribis ĝin.
Ĉu tiu estas blanka aux blanka.
Do vi volas aldoni ŝin probable tie ĉar se la grandeco is--
se tiuj estas tute plena, vi volas aldoni ĝin ĉi tie, ĉu ne?
>> Kaj tiel tio estas, dum tre, tre simpla, tute ne ĉiam ĝusta
ĉar la ĉefa diferenco inter vosto kaj pilo
estas ke la vosto povas reale manipulitaj
tiel ke la kapo ŝanĝoj depende kie vi volas
la komenco de via cue komenci.
Kaj kiel rezulto, via vosto Ankaŭ tuj ŝanĝos.
Kaj do rigardu tiu kodo nun.
Kiel vi uloj ankaŭ demandis al skribi sur la kvizo, enqueue.
Eble ni parolos tra kial la respondo estis kio estis.
>> Mi ne tute konvenas ĉi linion sur unu, sed esence tio koderon
devus esti sur unu linio.
Elspezi kiel 30 sekundoj.
Rigardu kaj vidu kial tiu estas la vojo kiu estas.
>> Tre, tre simila struct, tre, tre similan strukturon kiel la antaŭa
pilo krom eble unu linio de kodo.
Kaj ke unu linio de kodo determinas la funcionalidad.
Kaj vere diferencas atendovico de pilo.
>> Ĉiu volas preni ponardopiko ĉe klarigante kial vi havas
akiris ĉi komplika afero tie ĉi?
Ni vidas la revenon de nia mirinda amiko modulo.
Kiel vi uloj Baldaŭ venos rekoni en programado,
preskaŭ anytime vi bezonas ion volvi ĉirkaŭ io,
modulon tuj estos la maniero fari ĝin.
Do sciante ke, ĉu iu volas provi klarigi tiun linion de kodo?
Jes, ĉiuj respondoj estas akceptita kaj bonvenon.
Spektantaro: Ĉu vi parolas al mi?
ANDI PENG: Yeah.
Publiko: Ho, ne bedaŭras.
ANDI PENG: Bone, do ni marŝi tra tiu kodo.
Do kiam vi provas aldoni ion sur atendovico,
en la bela kazo ke la kapo okazas esti tie, ĝi estas tre facila por ni
nur iri al la fino enmeti ion, ĉu ne?
Sed la tuta punkto de atendovico estas ke la kapo povas fakte dinamike
ŝanĝi dependanta sur kie ni volas la komenco de nia q esti,
kaj kiel tia, la vosto Ankaŭ tuj ŝanĝos.
>> Kaj do imagi ke tiu ne estis la atendovico, sed prefere tiu estis la vico.
Diru la estro estas ĉi tie.
Diru nia queue similis tion.
Se ni volis movi kie la komenco de la linio estas,
diru ni ŝanĝis kapo unuflanken kaj grandecoj tie.
>> Nun ni volas aldoni ion al tiu vosto, sed kiel vi uloj povas vidi,
ĝi ne estas tiel simpla kiel simple aldonu kiom estas post la grandeco
ĉar tiam ni kuras el limojn de nia fakta tabelo.
Kie ni volas vere aldonas estas tie.
Jen la beleco de atendovico koncernas nin, vide ĝi
aspektas kiel la linio iras tiel, sed kiam stokitaj en datumstrukturo,
ili doni ĝin kiel kiel ciklo.
Ĉio envolvas ĉirkaŭ al la fronto la sama maniero
ke linio povas ankaŭ ĉirkaŭfermi ĉirkaŭ depende kie vi
volas komenco de la linio esti.
Kaj do se ni prenas rigardi malsupren tie, ni
diru ni volis krei funkcio nomita enqueue.
Ni volis aldoni int n enen ke q.
Se q.size q-- ni vokos ke niaj datumoj structure-- se nia queue.size ne
egala al kapacito aŭ se ĝi estas malpli ol kapablo,
q.strings estas la tabelo ene nia q.
Ni tuj starigis ke egalas q.heads,
kiu estas dekstre tie, plus q.size modulon per la kapablo, kiun
ĉirkaŭfermi nin reen ĉirkaŭ tie.
>> Do en tiu ekzemplo, indekso de kapo estas 1, ĉu ne?
La indekso de grandeco estas 0, 1, 2, 3, 4.
Do ni povas fari 1 plus 4 modulo per nia kapablo kiu estas 5.
Kion tio al ni?
Kio estas la indico kiu venas el tio?
>> Publiko: 0.
>> ANDI PENG: 0, kiu hazarde estas ĉi tie,
kaj tiel ni volas povi enmeti en ĝuste ĉi tie.
Kaj do ĉi tie ekvacio speco de nur funkcias kun ajna nombroj
depende kie via kapo kaj via grandeco estas.
Se vi scias kion tiuj aferoj, vi scias
ĝuste kie vi volas enigi kiom estas post via vico.
Ĉu tio havas sencon por ĉiuj?
>> Mi konas ia cerba teaser Precipe pro tio
venis en la sekvo de via kvizo.
Sed espereble ĉiuj nun povas kompreni
kial tiu solvo aŭ tiun funkcio estas la maniero ke ĝi estas.
Ĉiu iom neklara sur tio?
BONE.
>> Kaj tial nun, se vi volis dequeue, ĉi
estas kie nia kapo estus sxangxigxantaj ĉar se ni devis dequeue,
ni ne demetas la fino de la q.
Ni volas demeti la kapon, ĉu ne?
Do rezulte, kapo tuj ŝanĝos, kaj tial kiam vi enqueue,
vi devas sekvigi kie via kapo kaj via grandeco
estas povi enŝovi en la ĝusta pozicio.
>> Do kiam vi dequeue, Mi ankaŭ _Pseudocode_ ĝin.
Bonvolu se vi deziras provu kodigo ĉi ekstere.
Vi volas movi la kapon, ĉu ne?
Se mi volis dequeue, mi movus la kapon super.
Ĉi tiu estus la kapo.
>> Kaj nia nuna grandeco volus subtrahi ĉar ni ne plu
havas kvar elementoj en la tabelo.
Ni nur havas tri, kaj poste ni volas reveni ajn estis stokita interne
de la kapo ĉar ni volas preni tiun valoro el tiel tre similaj al la stako.
Nur vi prenas el malsama loko,
kaj vi havas religi vian montrilon al malsama loko kiel rezulto.
Logike, ĉiuj sekvas?
Granda.
>> Bone, do ni iras por paroli iomete pli en profundo pri ligitaj listoj
ĉar ili estos tre, tre valora por vi en la paso de ĉi tiu semajno
psets.
Ligitaj listoj, kiel vi infanoj povas memori, ili cxiuj,
estas nodoj kiuj estas nodoj de certaj valoroj de ambaŭ valoro kaj puntero
ke kunligitaj per tiujn punteros.
Kaj tial la struct en kiel ni krei nodon tie estas ni
havas int n, kiu estas kio ajn la valoron en oni tendencas aŭ ŝnuro n
aŭ kion ajn vi volas nomas ĝin, la char stelo n.
Struct nodo stelo, kiu estas la montrilon ke vi volas havi en ĉiu nodo,
vi tuj havos tiun puntero punkton al proksimaj.
Vi havos la kapo de ligillisto tio
tuj atentigi al la cetera la valoroj tiel plu kaj tiel plu
ĝis eventuale atingi la finon.
Kaj ĉi lasta nodo estas nur tuj ne havas puntero.
Ĝi tuj celi nula, kaj tio estas kiam
vi scias ke vi trafis la fino de via ligitaj listo
estas kiam via lasta montrilon ne notas al nenio.
>> Do ni tuj iru iom pli en profundo pri kiel oni farus eble
serĉu ligillisto.
Memoru kion estas iuj de la malavantaĝoj de la ligitaj listoj
versoj tabelo pri serĉoj.
Tabelo vi povas duuma serĉo, sed kial ne povas vin fari tion en ligillisto?
>> Publiko: Ĉar ili ĉiuj konektita, sed vi ne scias precize kie
[Inaudible].
>> ANDI PENG: Jes, ĝuste tial memoru ke la brilo de tabelo
estis la fakto ke ni devis senvica atingo memoro kie
se mi volus la valoro de indekso ses, mi povis nur diri indekso ses,
donu al mi tiun valoron.
Kaj tio estas ĉar tabeloj estas ordo en apuda spaco de memoro
en unu loko, dum speco de ligitaj listoj
estas hazarde intermetita ĉie, kaj la sola maniero vi povas trovi unu
estas per montrilo ke informas vin la adreso de kie tiu sekva nodo.
>> Kaj tiel kiel rezulto, la nura maniero serĉi tra ligillisto
estas lineara serĉo.
Ĉar mi ne ĝuste scias kie la 12-a valoro en la ligillisto estas,
Mi devas kruci la tuteco de tiu ligillisto unu
per unu el la kapo al la unua nodo, al la dua vertico, al la tria vertico,
tuta vojo malsupren ĝis mi finfine akiras al kie tiu nodo Mi serĉas estas.
Kaj tiel en tiu senco, serĉo sur ligillisto estas ĉiam n.
Ĉiam n.
Ĉiam en lineara tempo.
>> Kaj tial la kodo en kiu ni efektivigu tiun, kaj tiu
estas iom nova por vi uloj ĉar vi infanoj ne vere parolis aŭ iam
vidita punteros en kiel traserĉi punteros,
do ni trairu ĉi tre, tre malrapide.
Do bool serĉo, dekstra, imagu ni volas
krei funkcion nomita serĉo kiu revenas vera
se vi trovis valoron ene la ligitaj listo, kaj False alie.
Nodo stelo listo estas Nuntempe nur la montrilon
al la unua ero en via ligitaj listo.
int n estas la valoro kiun vi estas serĉanta en tiu listo.
>> Do nodo stelo puntero egalas listo.
Tio signifas ke ni opcio kaj kreante montrilon
al tiu unua nodo ene de la listo.
Ĉiu kun mi?
Do se ni devis iri tien, mi havus
pravalorizitaj montrilo kiu indikas al la kapo de kio ajn tiu listo estas.
>> Kaj tiam unufoje vi akiras ĉi tie, dum montrilon ne egala NULL,
tiel ke estas la buklo en kiu ni estas tuj estos poste lauxiris
la resto de nia listo pro kio okazas kiam puntero egalas nula?
Ni scias ke ni have--
>> Spektantaro: [inaudible]
>> ANDI PENG: Ekzakte, do ni scias ke ni atingis la finon de listo, ĉu ne?
Se vi iros tien, ĉiu nodo devus esti montrante al alia nodo
kaj tiel plu kaj tiel plu ĝis vi batis eventuale
la vosto de via ligillisto, kiu havas puntero kiu ĵus
ne notas ie alia ol neniu.
Kaj tial vi scias ke esence via listo estas ankoraŭ tie supren
ĝis montrilon ne egala nulaj ĉar iam ĝi egalas nula,
vi scias ke estas nenia pli aĵoj.
>> Do kiu estas la buklo en kiu ni estas tuj havos la fakta serĉo.
Kaj se la pointer-- ĉu vi vidas tian sagon funkcio ekzistas?
Do se puntero punktoj al n, se la montrilo ĉe n egalas egalas n,
por ke signifas ke se la puntero kiu vi estas
serĉanta sur la fino de ĉiu nodo estas fakte egala al la valoro
vi serĉas, tiam Vi volas reveni vera.
Do resume, se vi estas ĉe nodo ke havas la valoron, ke vi serĉas,
vi scias, ke vi estis povis sukcese serĉu.
>> Alie, vi volas agordi vian sagon al la sekva nodo.
Tion tiun linion tie faras.
Puntero egalas puntero sekva.
Cxiu komprenas kiel tio funkcias?
>> Kaj esence vi tuj nur kruci la tuteco de la listo,
rekomenciganta via puntero ĉiu tempo ĝis vi finfine atingis la finon de la listo.
Kaj vi scias, ke ne ekzistas pli nodoj al traserĉi,
kaj tiam vi povas reveni falsaj ĉar vi scias ke, ho, nu,
se mi povis serĉi tra la tuteco de la listo.
Se en ĉi tiu ekzemplo, se mi volus serĉi la valoro de 10,
kaj mi komencos je la kapo, kaj Mi traserĉos la vojo malsupren,
kaj mi fine atingis tion, kio puntero kiu notas al nula,
Mi scias ke, crap, mi supozas 10 Ne en tiu listo ĉar mi ne povis trovi ĝin.
Kaj mi estas fine de la listo.
Kaj tiaokaze vi scias Mi tuj revenos falsaj.
>> Lasu ke trempi en ĉar iomete.
Tiu estos bela grava por via pset.
La logiko de tio estas tre simpla, eble sintakse ĵus efektiviganta ĝin.
Vi infanoj deziras fari certas ke vi komprenos.
Malvarmeta.
>> OK, do kiel ni estus enmeto nodoj, dekstra,
en listo ĉar memori kio estas la kiom da avantaĝoj
havi ligillisto kontre tabelo en terminoj de stokado?
>> Spektantaro: Ĝi estas dinamika, do ĝi estas pli facile to--
>> ANDI PENG: Precize, do ĝi estas dinamika, kiu
signifas ke ĝi povas pligrandigi kaj retiri dependanta sur la uzanto bezonoj.
Kaj tiel, en tiu senso, ni ne bezonas malŝpari nenecesa memoro ĉar mi
se mi ne scias kiom da valoroj Mi volas al vendejo, ĝi ne havas sencon por mi
krei tabelo ĉar se mi volas konservi 10 valoroj
kaj mi kreos tabelo de 1.000, jen multajn malŝparita memoro, donitan.
Tial ni volas uzi kunligita listo por povi dinamike
ŝanĝi aŭ ŝrumpi nia grandeco.
>> Kaj tial faras inserción iom pli komplikita.
Ĉar ni ne povas aliri hazarde elementoj la vojo, ke ni devus de tabelo.
Se mi volas enmeti ero en la sepa indekso,
Mi nur povas enmeti ĝin en la sepa indekso.
Sur ligillisto, ĝi ne tute labori kiel facile,
kaj do se ni volas enmeti la tie en la ligillisto,
vide, ĝi estas tre facile vidi.
Ni nur volas enmeti ĝin ĝuste tie, ĝuste en la komenco de la listo,
dekstra post kapo.
>> Sed la maniero en kiu ni havas religi la punteros estas iom malsimpla
aŭ, logike, ĝi havas sencon, sed Vi volas certigi ke vi havas ĝin
tute malsupren ĉar la lasta afero vi volas
estas religi puntero la maniero ke ni faras ĉi tie.
Se vi dereference la montrilo de la kapo ĝis 1,
tiam subite la resto de via ligitaj listo
estas perdita ĉar vi havas ne reale kreis provizoran nenion.
Jen montris la 2.
Se vi preferas religi la montrilo, tiam la resto de via listo estas tute perdita.
Do vi deziras esti tre, zorgoplenaj
unue atribui la montrilo el ajn vi
volas enmeti en kie ajn vi volas, kaj tiam vi
povas dereference la resto de via listo.
>> Do ĉi validas por kien vi provas enmeti en.
Se vi volas enigi ĉe la kapo, se vi volas respondi tie,
se vi volas enmeti en Fine, nu, fine mi
divenu vi simple ne havas puntero, sed vi
volas certigi ke vi ne perdi la reston de via listo.
Vi ĉiam volas certigi via nova nodo notas
al kio ajn vi volas enmeti en,
kaj tiam vi povas aldoni la ĉenante plu.
Ĉiu klara?
>> Ĉi tuj estos unu el la veraj temoj.
Unu de la plej gravaj aferoj vi tuj havos sur via pset
estas ke vi tuj provi krei ligillisto kaj enigaĵo aferoj
sed tiam simple perdi la resto de via ligitaj listo.
Kaj vi tuj estos kiel mi ne scias kial tio okazas?
Kaj ĝi estas doloro trapasi kaj serĉi ĉiun de viaj indikoj.
>> Kaj mi garantias vin sur ĉi pset, skribado kaj desegnado tiuj nodoj eksteren
estos tre, tre helpema.
Do vi povas tute sekvigi de kie ĉiuj viaj indikoj estas,
kio okazas erara, kie ĉiuj nodoj estas via,
kion vi bezonas fari por aliri aŭ enmeti aŭ forigi aŭ ajna de ili.
Ĉiu bona kun tiu?
Malvarmeta.
>> Do se ni volis rigardi la kodon?
Ho, mi ne scias se ni povas vidi the-- Bone, do
ĉe la supro ĉiu estas estas funkcio nomita insert kie ni volas
enmeti int n en la ligillisto.
Ni tuj trairu ĉi.
Ĝi estas multe da kodo, multan novan sintakson.
Ni estos OK.
>> Do supren ĉe la supro, kiam ajn ni volas krei ion
kion ni devas fari, Precipe se vi deziras ĝin ne esti stokitaj sur la stako
sed en la amaso?
Ni iras al malloc, dekstra?
Do ni tuj krei puntero.
Nodo, montrilo, novaj egaluloj malloc la grandeco de nodo
ĉar ni volas ke nodo estu kreita.
Ni volas la kvanto de memoro kiu nodo dissxutas
esti asignita por la kreo de la nova nodo.
>> Kaj tiam ni tuj kontrolu ĉu nova egaluloj egalas nula.
Memoru kion ni diris?
Kion ajn vi malloc, Kion vi devas ĉiam fari?
Vi devas ĉiam kontroli por vidi ĉu aŭ ne ke estas nula.
>> Ekzemple, se via mastruma sistemo estis tute plena,
se vi jam ne havis memoron ĉe ĉiuj kaj vi provas malloc,
revenus nula por vi.
Kaj do se vi provas uzi ĝin kiam montrante al nula,
vi ne tuj povis aliri tiun informon.
Do kiel tia, ni volis fari certas ke kiam ajn vi mallocing,
vi ĉiam kontrolas, ĉu tiu memoro, al vi estas nula.
Kaj se ĝi ne estas, tiam ni povas movi sur kun la resto de nia kodo.
>> Do ni tuj pravalorizi la nova nodo.
Ni tuj faros novan n egalas n.
Kaj tiam ni tuj faros metis novajn la montrilo sur nova
al nula ĉar nun ni ne volas nenion por ŝi atentigi al.
Ni ne scias kien ĝi tuj metos vin,
kaj tiam se ni volas enmeti ĝin ĉe la kapo,
tiam ni povas reassign la sagon al la kapo.
Ĉu ĉiuj sekvi la logikon de kie ke okazas?
>> Ĉiuj ni faras estas kreante nova nodo, fiksanta la montrilon al nula,
kaj tiam reassigning ĝin al la kapo se ni
scias ni volas enmeti gxin en la kapo.
Kaj tiam la kapo tuj atentigi al tiu nova nodo.
Ĉiu OK kun tiu?
>> Do estas du-paŝa procezo.
Vi devas atribui unua ajn vi kreas.
Ŝanĝu ke puntero al la referenci kaj tiam vi
povas ia dereference la unua montrilo
kaj punkto al la nova nodo.
Kie ajn vi volas enigi ĝin, ke logiko tuj teni vera.
>> Estas ia kiel asignanta temporal variablo.
Memoru, vi havas certigi ke vi
ne perdas trakon de se vi interŝanĝante.
Vi volas certigi ke vi havas temporal variablo tian tenas
trako de kie tiu afero estas stokita por ke vi
ne perdas neniun valoron en la kurso de kiel rompado ĉirkaŭe kun ĝi.
>> Bone, do kodo estos tie.
Vi uloj rigardu post sekcio.
Estos tie.
>> Do mi supozas kiel faras ĉi diferenciĝas se ni volis
enmeti en la mezo aŭ la fino?
Ĉu iu havas ideon pri kio estas la _pseudocode_ kiel la logika referenco
ke ni prenus se ni volis enmeti ĝin en la mezo?
Do se ni volis enmeti ĝin ĉe la kapo, ĉiuj ni faras estas krei nova nodo.
Ni starigu la montrilo de tiu nova nodo al kiom la kapo,
kaj poste ni almetis la kapon al la nova nodo, ĉu ne?
Se ni volis enmeti ĝin en la mezo de la listo, kion ni devas fari?
>> Spektantaro: estus ankoraŭ esti simila procezo
de kiel asignanta puntero kaj tiam asignanta ke puntero,
sed ni devus loki tie.
>> ANDI PENG: Ekzakte, do precize la sama procezo krom vi
devas lokalizi kie ekzakte vi volas ke novaj montrilon al internigi,
do se mi volas enmeti en la mezo de ligitaj list-- OK,
diru ke estas nia ligillisto.
Se ni volas enmeti ĝin ĉi tie, ni iras al krei novan nodon.
Ni tuj malloc.
Ni tuj kreos novan nodon.
Ni tuj asigni la montrilo de tiu nodo tie.
>> Sed la problemo kiu diferencas de kie la kapo estas
estas ke ni sciis ĝuste kie la kapo estas.
Estis ĝuste en la unua, ĉu ne?
Sed tie ni devas konservi trako de kie ni enmeto ĝin.
Se ni enmeto nia nodo tie, ni havas
certigi ke la unu antaŭa al tiu nodo
Estas kiu reassigns la montrilo.
Tial do vi devas ia sekvigi du aferoj.
Se vi konservi trako de kie tiu nodo aktuale estas enmeto en.
Vi ankaŭ devas konservi trako de kie la antaŭa nodo ke vi rigardas
estis ankaŭ tie.
Ĉiu bona kun tiu?
BONE.
>> Kion pri enmeto en la fino?
Se mi volis aldoni ĝin here-- se mi volus aldoni novan nodon al la fino de listo,
kiom povus mi iras pri faranta tion?
Publiko: Do ​​nuntempe, la lasta onies indikis nula.
ANDI PENG: Yeah.
Precize, do ĉi tiu aktuale estas pinta scii,
kaj do versxajne, en tiu senco, estas tre facile aldoni al la fino de listo.
Ĉiuj vi devas fari estas starigis ĝin egala al nula kaj tiam Eksplodo.
Dekstre, tre facila.
Tre simpla.
>> Tre simila al la kapo, sed logike vi
volas certigi ke la paŝoj vi prenas al fari ion el tiu,
vi sekvajn kune.
Estas tre facile, en la mezo de via kodo, akiri kaptita supre sur,
ho, mi havas tiom da montriloj.
Mi ne scias kie io estas indikante.
Mi eĉ ne scias kiu nodo Mi estas sur.
Kio okazas?
>> Relax, trankviligi, prenu profunda spiro.
Eltiru vian ligillisto.
Se vi diras, mi scias, kie ĝuste Mi bezonas enmeti ĉi en
kaj mi scias precize kiel religi mian punteros, multe, multe pli facile bildigi
fjordon multe, multe pli facile ne perdiĝi en la cimoj de via kodo.
Ĉiu OK kun tiu?
BONE.
>> Do mi supozas estas koncepto kiun ni havas ne vere priparolis antaŭ nun,
kaj mi supozas ke vi probable ne renkontas multe yet--
ĝi estas speco de progresinta concept-- estas ke ni efektive havas datumojn
strukturo nomiĝas duoble ligitaj listo.
Do kiel vi uloj povas vidi, ĉiuj ni faras estas kreante
fakta valoro, ekstra montrilon sur ĉiu el niaj nodoj
kiu ankaŭ notas al la antaŭa nodo.
Do ne nur ni havas niajn nodoj atentigi al la venonta unu.
Ili ankaŭ indikas la antaŭa.
Mi tuj ignori tiujn du nun.
>> Sekve vi cxeno kiu povas movi ambaŭ manieroj,
kaj tiam ĝi estas iom pli facile al logike sekvi kune.
Kiel tie, anstataŭ konservanta trako de, ho, mi
devas scii ke ĉi tiu nodo estas kiu mi devos religi,
Mi povas nur iri tien kaj nur tiri la antaŭa.
Tiam mi scias precize kie tio estas, kaj tiam vi
ne devas trairi la tuteco de la ligitaj listo.
Estas iom pli facile.
>> Sed kiel tiaj, vi havos duoble la kvanto de punteros,
jen duobla la kvanto de memoro.
Estas multaj indikoj spuri.
Estas iom pli kompleksaj, sed estas iom pli uzanto amika depende
sur kion vi provas sukcesi.
>> Do tiu tipo de datumoj strukturo totalmente ekzistas,
kaj la strukturon por estas tre, tre simpla krom ĉiuj vi devi estas,
anstataŭ simple montrilo al proksima, vi ankaŭ havas montrilon por antaŭa.
Jen ĉio la diferenco estis.
Ĉiu bona kun tiu?
Malvarmeta.
>> Bone, do nun mi estas por vere elspezi probable
kiel 15 al 20 minutoj aŭ la plejparton de la resto de la tempo en sekcio
parolante pri hash tabloj.
Kiel multaj el vi infanoj legis pset5 specifon?
Bone, bone.
Jen altaj ol la 50% de normale.
Estas bone.
>> Do kiel vi infanoj vidos, vi estas defio en pset5
Estos implementar vortaron kie vi ŝarĝi super 140.000 vortoj
ke ni donu al vi kaj literumilo ĝin kontraŭ la tuta de la teksto.
Ni donos al vi hazarda pecoj de literaturo.
Ni donos al vi La Odiseado.
Ni donos al vi La Iliado.
Ni donos al vi Austin Powers.
>> Kaj via defio Estos por literumilo
ĉiu unuopa vorto en ĉiu de tiuj vortaroj
esence kun niaj literumilo.
Kaj tiel ekzistas kelkaj partoj krei ĉi pset,
unue vi volas esti povis reale ŝarĝi
ĉiuj vortoj en vian vortaro, kaj tiam vi
deziras povi literumilo ĉiuj ili.
Kaj tiel kiel tiaj, vi tuj postuli datumstrukturo kiu povas fari tion rapide
kaj kompetente kaj dinamike.
>> Do mi supozas la plej facila maniero fari tion, vi
verŝajne krei tabelon, dekstra?
La plej facila maniero de stokado estas vi povas krei tabelon de 140.000 vortoj
kaj simple meti ilin ĉiuj tie kaj tiam kruci ilin per duuma serĉo
aŭ por selektadoj aŭ not-- bedaŭras ke estas ordigado.
Vi povas ordigi ilin kaj tiam kruci ilin per duuma serĉo aŭ nur lineara serĉo
kaj nur finaj vortoj, sed ke prenas grandegan kvanton da memoro,
kaj ĝi ne estas tre efika.
>> Kaj tial ni tuj komencos parolas pri manieroj de farado
nia rultempo pli efika.
Kaj nia celo estas atingi konstanta tempo kie
Estas preskaŭ kiel sensilo, kie vi havos tujan aliron.
Se mi volis serĉi ion, Mi volas povi ĝuste,
eksplodo, trovas ĝin ĝuste, kaj tiri ĝin ekstere.
Kaj tiel strukturo en kiu ni estos igante tre proksima
por povi aliri konstanta tempo, tiu sankta grail
en programado de konstanta tempo nomata hash tablo.
Kaj David antaŭe menciita la [Inaudible] iomete en prelego,
sed ni tuj vere plonĝo en profunda tiu semajno
sur peco kiu estas rilate kiom hash tablo funkcias.
>> Do la vojo ke hash tablo verkoj, ekzemple,
se mi volis konservi aron da vortoj, faskon da vortoj en la angla lingvo,
Mi povus teorie metis banano, pomo, kivo, tenilo, paro,
kaj melono ĉiuj sur nur tabelo.
Cxiuj povis havi en kaj esti trovi.
Estus speco de doloro serĉu tra kaj aliro,
sed la facila maniero fari tiun estas ke ni povas krei fakte strukturo
nomata hash tablo kie nin hash.
Ni kuras ĉiujn de niaj klavoj tra hash funkcio, ekvacio,
kiu igas ilin ĉiujn en ia valoro
ke poste ni povos stoki sur esence tabelo de ligillisto.
>> Kaj do ĉi tie, se ni volis stoki anglaj vortoj,
ni povis potenciale simple, mi ne faras scias, turni ĉiujn unua literoj
en ia nombro.
Do, ekzemple, se mi volus A esti sinonimo apple--
aŭ kun la indico de 0, kaj B esti sinonima kun 1,
ni povas havi 26 eniroj kiu povas nur stoki
ĉiuj leteroj de la alfabeto kiu ni komencos kun.
Kaj tiam ni povas havi pomo je la indekso de 0.
Ni povas havi banano ĉe la indico de 1, melono ĉe la indico de 2,
kaj tiel plu kaj tiel antaŭen.
Kaj tiel, se mi volis serĉi miaj hash tablo kaj aliro pomo,
Mi scias pomon komenciĝas per A, kaj mi scias precize
ke ĝi devas esti kaj la hash tablo ĉe indekso 0 ĉar
de la funkcio antaŭe asignita.
>> Do mi ne scias, ni uzanto programo kie
vi estos akuzita arbitrarily-- ne arbitre,
kun provanta pensoplene elpensi bonan ekvacioj
povi disvastigi el ĉiuj viaj valoroj
en maniero ili povas facile aliri ĝin poste kun kiel ekvacio
ke vi mem scias.
Do en tiu senco, se mi volis iri al mango, mi scias, ho, ĝi komenciĝas kun m.
Devas esti ĉe la indico de 12.
Mi ne devas traserĉi nenion.
Mi scias exactly-- mi povus nur iri al la indekso de 12 kaj tiri ke ekstere.
>> Ĉiu klara pri kiel oni hash tablo funkcio laboras?
Estas speco de nur pli kompleksa tabelo.
Jen ĉio estas.
BONE.
>> Do mi supozas ke ni renkontas tiu demando de kio
okazas se vi havas plurajn aferojn kiuj donas vin la sama indico?
Do diru nia funkcio, ĉiuj ĝi faris estis preni tiun unuan literon
kaj turni kiuj en respektiva 0 tra 25 indekso.
Tio estas tute bone se vi nur havas unu de ĉiu.
Sed la dua vi komencas havante pli, vi estas
tuj havas kio nomiĝas kolizio.
>> Do se mi provas enmeti enterigi en hash tablo kiu jam havas bananon sur ĝi,
kio okazos kiam vi provas enmeti tio?
Malbonaj aferoj ĉar banano jam ekzistas ene de la indekso
ke vi volas konservi ĝin en.
Bero ia similas, ha, kion mi faru?
Mi ne scias kien iri.
Kiel mi solvi ĉi?
>> Do vi infanoj volas ia vidu ni faros ĉi delikata afero
Kie ni povas ia reale krei ligillisto en niaj tabeloj.
Kaj do la plej facila vojo pensi pri tio,
ĉiuj hash tablo estas tabelo de ligitaj listoj.
Kaj tiel, en tiu senco, vi devos tiu bela tabelo de punteros,
kaj tiam ĉiu montrilon en ke valoro, en tiu indekso,
povas fakte indiki al aliaj aferoj.
Kaj tial vi havas ĉiujn tiujn apartajn ĉenoj elspezi de unu granda tabelo.
>> Kaj do ĉi tie, se mi volis enmeti bero,
Mi scias, OK, mi tuj enigo ĝin tra mia hash funkcio.
Mi tuj finos kun la indico de 1, kaj tiam mi tuj povos havi
nur malgrandan subaron de tiu giganto 140.000-vorto vortaro.
Kaj tiam mi povas nur rigardi tra 1/26 de tiu.
>> Kaj tiel do mi povas simple enŝovi bero aŭ antaŭ aŭ post banano
en tiu kazo?
Post, dekstra?
Kaj do vi tuj volas enmeti ĉi nodo post banano,
kaj tiel vi tuj enmeti ĉe la vosto de tiu ligillisto.
Mi tuj iros reen al tiu antaŭa glitejo,
do vi uloj povas vidi kiel hash funkcio laboras.
>> Do krada funkcio estas tiu ekvacio ke vi uzas specon de via enigo
tra akiri ajn indekso vi volas atribui al ĝi.
Kaj tiel, en tiu ekzemplo, ĉiuj ni volis fari estis preni la unua litero,
igi tiun en indekso, tiam ni povas stoki ke en nia hash funkcio.
Ĉiuj ni faras ĉi tie estas ni konvertanta la unua litero.
Do keykey [0] estas nur la unua litero sendistinge kordoj ni havas,
ni pasante en.
Ni konvertas ke al supra, kaj ni forprenante per majuskla A,
do ĉiuj kiuj faras donas al ni kelkajn
en kiu ni povas hash niajn valorojn sur.
>> Kaj tiam ni tuj reveni hash modulo grandeco.
Estu tre, tre zorgema ĉar, teorie, tie
via hash valoro povis esti malfinio.
Ĝi povus simple daŭrigi kaj sur kaj sur.
Ĝi povus esti kelkaj vere, vere granda valoro,
sed ĉar via hash tablo ke vi kreis nur havas 26 indeksas,
Vi volas certigi vian modulusing por ke vi
ne run-- ĝi estas la sama aĵo kiel via queue--
por ke vi ne kuras ekstere la fundo de via hash funkcio.
>> Vi volas enpaki ĝin ĉirkaŭ sammaniere en [inaudible] kiam
vi havis kiel tre, tre grandan leteron, vi
ne volis ke al nur kuri for la fino.
Sama afero ĉi tie, vi volas certigi ĝi ne kuras for la fino envolviendo
ĉirkaŭ la supro de la tablo.
Do tio estas nur tre simpla hash funkcio.
Ĉiuj kiuj faris estis preni la unuan letero de whatever niaj enigo estis
kaj turni kiuj en indico kiu Ni povus meti en niajn hash tablo.
>> Yeah, kaj tiel kiel mi diris antaŭe, la vojo, ke ni solvi kolizioj
en nia hash tabloj estas havanta, kion ni nomas, ĉenante.
Do se vi provas enmeti plurajn vortoj kiuj komenciĝas kun la sama afero,
vi tuj havos unu hash valoro.
Aguacates kaj pomon, se vi havas ruli ĝin per nia hash funkcio,
tuj donos al vi la sama nombro, la nombro de 0.
Kaj tial la maniero kiun ni decidu, ke estas ke ni povas efektive ia ligas ilin
kune tra ligitaj listoj.
>> Kaj tiel en tiu senco, vi uloj povas vidi specon
de kiel datumstrukturoj ke ni estis fiksanta antaŭe
kiel sekvinberoj ligillisto speco de povas kunvenos.
Kaj tiam vi povas krei multe pli efika datumstrukturoj
kiu povas manipuli grandajn kvantojn de datumoj, kiuj dinamike regrandigi depende
sur viaj bezonoj.
Ĉiu klara?
Ĉiu speco de klara kio okazas ĉi tie?
>> Se mi volis insert-- kio estas frukto kiu komenciĝas per, mi ne scias,
B, aliaj ol bero, banano.
>> Publiko: Blackberry.
>> ANDI PENG: Blackberry, rubuso.
Kie rubusbero iras tien?
Nu, ni fakte ne ordo ĉi ankoraŭ, sed teorie
se ni volus havi tiun en alfabeta ordo,
kie devus BlackBerry iras?
>> Spektantaro: [inaudible]
>> ANDI PENG: Precize, post ĉi tie, ĉu ne?
Sed ĉar ĝi estas tre malfacile reorder-- Mi supozas lin tuŝas al vi uloj.
Vi uloj povas tute apliki kion vi volas.
La pli efika maniero fari tion eble
estus ordigi vian ligitaj listo en alfabeta ordo,
kaj do kiam vi estas enmeto aferoj, vi volas
certi enigi ilin en alfabeta ordo
por ke poste kiam vi estas provas serĉi ilin,
vi ne devas trairi ĉiu.
Vi scias precize kie ĝi estas, kaj ĝi estas pli facila.
>> Sed se vi ia havas aferojn intermetita hazarde,
vi ankoraŭ havos al _traverse_ ĝi anyways.
Kaj do se mi volis nur enmeti rubusbero tie
kaj mi volis serĉi ĝi, mi scias, ho, rubusbero
devas komenci kun la indico de 1, do mi scias instantáneamente nur serĉu ĉe 1.
Kaj tiam mi povas ia kruci la ligillisto
ĝis mi alvenas al BlackBerry, kaj then-- yeah?
>> Publiko: Se vi provas create-- Mi supozas kiel ĉi estas tre simpla hash
funkcio.
Kaj se ni volis fari multoblaj tavoloj de tiu kiel,
OK, ni volas apartigi en kiel ĉiuj alfabeta literoj
kaj tiam denove ŝati alia aro de alfabeta literoj ene de tiu,
ni metante kiel hash tablo ene hash tablo,
aŭ kiel funkcio ene funkcio?
Aŭ estas that--
>> ANDI PENG: Do via hash function-- via hash tablo
povas esti kiel granda kiel vi deziras ĝin.
Do en tiu senco, mi pensis gxi estas tre facila, tre
simpla por mi nur ia bazita sur literoj de la unua vorto.
Do ekzistas nur 26 eblojn.
Mi povas nur akiri 26 ebloj de 0 ĝis 25 ĉar ili povas nur
komenci de A ĝis Z. Sed Se vi volis aldoni, eble, pli komplekseco
aŭ rapida kuri tempo por via hash tablo, vi absolute
povas fari ĉiajn aferojn.
Vi povas fari vian propran ekvacio kiu donas
pli dissendo en via vortoj, tiam kiam vi serĉi,
ĝi tuj estos pli rapida.
>> Ĝi estas tute ĝis vi infanoj kiom vi volas apliki tion.
Pensu pri ĝi kiel ĵus siteloj.
Se mi volus havi 26 siteloj, mi tuj
ordigi aferojn en tiuj siteloj.
Sed mi tuj havas faskon de aĵoj en ĉiu sitelo
do se vi volas fari ĝin rapida kaj pli efika,
mi havas cent sitelojn.
>> Sed tiam vi devas eltrovi maniero ordigi aferojn tiel ke ili estas
en la konvena sitelo ili devus esti en.
Sed tiam kiam vi efektive volas rigardi ke sitelo
ĝi estas multe pli rapida ĉar tie estas malpli havajxoj en ĉiu sitelo.
Do, jes, tio estas vere la lertaĵo por vi uloj en pset5
estas ke vi estos defiita simple krei
kiom estas la plej efika funkcio povas pensi ke
povi stoki kaj kontroli tiujn valorojn.
>> Tute supren al vi infanoj tamen vi volas fari ĝin,
sed tio estas vere bona punkto.
Ke tia logiko vi volas komenci pensi pri
estas, nu, kial ne mi faras pli siteloj.
Kaj tiam mi devos serĉi malpli aĵoj, kaj tiam eble mi
havas malsaman hash funkcio.
>> Jes, ekzistas multe da manieroj fari tion pset, iuj estas pli rapida ol aliaj.
Mi tute tuj ĝuste vidi kiel rapida estis la plej rapida vi infanoj estos
povos akiri vian funkciojn labori.
OK, ĉiuj bone sur ĉeni kaj hash tabloj?
Ĝi estas fakte kiel tre simpla koncepto se vi pensas pri ĝi.
Ĉiuj estas estas disigante ajn viaj enigoj estas en siteloj,
ordigado de ili, tiam serĉanta la listas ke estas asociita kun.
>> Malvarmeta.
Bone, nun ni havas malsaman specon de datuma strukturo kiu nomiĝas arbo.
Ni plu iru kaj parolu pri tries kiuj estas klare malsamaj,
sed en la sama kategorio.
Esence, ĉiu arbo estas anstataŭe organizi datumojn en la maniero lineal
ke hash tablo does-- vi Sciu, ĝi estas atingis supro kaj fundo
kaj tiam vi ia ligi ekstere de it-- a arbo havas maksimuman kiun vi nomas la radiko,
kaj tiam ĝi havas foliojn tute ĉirkaŭ ĝi.
>> Kaj do ĉiuj vi havas ĉi tie estas nur la pinta nodo
kiu notas al aliaj nodoj, kiuj punktoj al pli nodoj, kaj tiel plu kaj tiel antaŭen.
Kaj tial vi nur devas forkiĝanta branĉoj.
Estas nur alia maniero de organizado datumoj, kaj ĉar ni nomas ĝin arbo,
vi uloj just-- estas nur modelita eksteren rigardi kiel arbo.
Tial ni nomas ĝin arboj.
>> Hash tablo aspektas kiel tablo.
Arbo nur aspektas kiel arbo.
Ĉiuj estas estas aparta maniero organizi nodoj
Dependanta sur kio viaj bezonoj estas.
>> Do vi havas radikon kaj tiam vi havas foliojn.
La maniero kiun ni povas aparte pensi pri ĝi estas duuma arbo,
duuma arbo estas nur specifa tipo de arbo
kie ĉiu nodo nur punktoj al, je maks, du aliaj nodoj.
Kaj do jen vi havas distingan simetrio en via arbo
ke faciligante ia rigardu ĉe kio aprezas vi estas ĉar tiam vi
havas ĉiam maldekstran aŭ dekstren.
Ekzistas neniam kiel maldekstra tria el maldekstren aŭ kvarono de la maldekstro.
Ĝi estas nur vi havas maldekstra kaj dekstra kaj vi povas serĉi aŭ de tiuj du.
Kaj do kial estas tiu utila?
La maniero ke tiu estas utila estas se vi serĉas
serĉi tra valoroj, dekstra?
Prefere ol efektivigado duuma serĉu en eraro tabelo,
se vi volis povi enigi nodoj kaj forigos nodoj ĉe volo kaj ankaŭ
konservi la serĉo kapabloj de duuma serĉo.
Do tiamaniere, ni estas speco de tricking-- memoras kiam ni
diris ligitaj listoj ne povas duuma serĉo?
Ni ia kreante datumstrukturo ke lertaĵoj ke en laboranta.
>> Kaj tiel ĉar ligitaj listoj estas linearaj, ili nur ligas unu post la alia.
Ni povas ia havas Alispeca punteros
ke punkto al malsamaj nodoj kiu povas helpi nin per serĉo.
Kaj do ĉi tie, se mi volus havas duuma serĉo arbo,
Mi scias ke miaj mezo se 55.
Mi simple tuj krei ke kiel mia mezo, kiel mia radiko,
kaj tiam mi iros al havi valoroj spin off de ĝi.
>> Do jen, se mi iros por serĉi la valoro de 66, mi povas komenci ĉe 55.
Estas 66 pli granda ol 55?
Jes ĝi estas, do mi scias mi mus serĉu I n la dekstra montrilo de tiu arbo.
Mi iros al 77.
OK, estas 66 malpli ol aŭ pli granda ol 77?
Ĝi estas malpli ol, tiel vi scias, ho, kiu devas esti la maldekstra nodo.
>> Do jen ni estas speco de konservado ĉiuj la grandaj aferoj pri arrays,
tiel kiel dinamika regrandigo de objektoj, estante
povos enmeti kaj forigi laŭvole, sen devi maltrankviligi la fiksa
kvanto de spaco.
Ni ankoraŭ konservas ĉiujn tiujn mirindaĵojn
dum ankaŭ povante konservi la ensaluti kaj serĉu tempo de duuma serĉo
ke ni nur antaŭe kapabla akiri frazo.
>> Cool datumstrukturo, ia kompleksa implementar, la nodo.
Kiel vi povas vidi, ĉiuj ĝi estas la struct de la nodo
estas ke vi havas maldekstre kaj dekstra montrilo.
Jen ĉio estas.
Do anstataŭ nur havanta x aŭ antaŭan.
Vi havas maldekstra aŭ dekstra, kaj tiam vi povas ia ligas ilin kune
tamen vi tiel elektos.
>> OK, Ni efektive tuj nur preni kelkajn minutojn.
Do ni tuj iru tien.
Kiel mi diris antaŭe, Mi specon de klarigis
la logiko malantaŭ kiel ni estus traserĉi ĉi.
Ni tuj provos pseudocoding ĉi ekstere al vidi
se ni povas ia apliki la sama logiko de binara serĉo
al malsama tipo de datumstrukturo.
Se vi infanoj volas preni kiel paro Minutoj ĵus pensas pri tiu.
BONE.
Bone, mi tuj efektive nur donas vin the-- ne,
ni parolos pri la _pseudocode_ unue.
Do ĉu iu volas doni ponardopiko ĉe kio
la unua afero vi deziras fari kiam vi elkomencanta serĉado estas?
Se ni serĉas la valoro de 66, kio estas
ni unue volas fari se ni volas duuma serĉo ĉi arbo?
>> Spektantaro: Vi volas rigardi dekstra kaj rigardu maldekstren kaj vidu [inaudible]
pli granda nombro.
>> ANDI PENG: Jes, ĝuste.
Do vi tuj rigardi vian radikon.
Ekzistas multaj manieroj vi povas nomi ĝin, via patro nodo homoj diras.
Mi ŝatas diri radiko ĉar jen kiel la radiko de la arbo.
Vi tuj rigardi via radika vertico, kaj vi estas
tuj vidos estas 66 grandaj ol aŭ malpli ol 55.
Kaj se ĝi estas pli granda ol, nu, tio estas granda ol, kie ni volas rigardi?
Kie ni volas serĉi nun, ĉu ne?
Ni volas serĉi dekstra duono de tiu arbo.
>> Do ni havas, oportune, a puntero kiu notas al la dekstra.
Kaj tiel do ni povas fiksi nia nova radiko esti 77.
Ni povas nur iri al kie ajn la puntero estas indikante.
Nu, ho, tie ni startanta ĉe 77, kaj ni povas nur
fari tion rekursie denove kaj denove.
Tiamaniere, vi afabla de havi funkcion.
Vi havas vojon de serĉado ke vi povas nur ripeti denove kaj denove kaj denove,
Dependanta sur kie vi volas rigardi ĝis vi fine atingos la valoro
ke vi estas serĉanta.
Sencon?
>> Mi volis montri al vi la fakta kodo, kaj ĝi estas multe da kodo.
Ne necesas Freak Out.
Ni parolos tra ĝi.
>> Efektive, ne.
Tiu estis nur _pseudocode_.
OK, ke estis nur la _pseudocode_, kio estas iom kompleksa,
sed estas tute bone.
Ĉiu sekvanta kune tie?
Se la radiko estas nula, reveno falsa pro tiu rimedo
vi eĉ ne havas tie ion.
>> Se radiko n estas la valoro, tial se ĝi hazarde estas la unu vi rigardas,
tiam vi tuj reveni vera ĉar vi scias ke vi trovis ĝin.
Sed se la valoro estas malpli ol radiko de n, vi estas
tuj serĉu maldekstre infano aŭ la maldekstra folio,
kion ajn vi volas nomi ĝin.
Se la valoro estas pli granda ol radiko, vi tuj serĉu la dekstra arbo,
tiam nur ruli la funkcio tra serĉo denove.
>> Se radiko estas nula, ke tiu signifas vi atingis la finon?
Tio signifas ke vi ne havas pli pli folioj esplori,
tiam sciu, ho, mi supozas ke ne tien
ĉar post mi rigardis tra la tuta afero kaj ĝi ne estas tie ĉi,
ĝi simple ne povus esti ĉi tie.
>> Ĉu tio havas sencon por ĉiuj?
Do estas kiel duuma serĉo konservante la kapabloj de ligitaj listoj.
Cool, kaj tiel la dua tipo de datumstrukturo vi infanoj
povas provi efektiviganta vian pset, Vi nur devas elekti unu metodo.
Sed eble alternativa metodo al la hash tablo estas kion ni nomas trie.
>> Ĉiuj trie estas estas specifa tipo de arbo kiun
havas valorojn kiuj iras al aliaj valoroj.
Do anstataŭ havi binaran arbo en la senco, ke nur unu
afero povas celi du, vi povas havi unu aferon punkto al multaj, multaj aĵoj.
Vi esence havas arrays ene de kiu vi stoki
punteros ke indikas aliaj tabeloj.
>> Do la nodo de kiel ni difinus trie
Estas ni volas havi Buleaj, c vorto, ĉu ne?
Do la nodo estas Bulea kiel vera aŭ falsa,
Unue ĉe la kapo de ke tabelo estas la jena vorto?
Due, vi volas havi punteros al kiom la resto de ili estas.
Iom komplika, iom abstrakta, sed Mi klarigos kion tio ĉiuj rimedoj.
>> Do jen, supre, se vi havas tabelo deklaris jam,
nodo kie vi havas Bulea valoro stokita en la fronto
kiu diras vin estas tiu vorto?
Ĉu tio ne estas vorto?
Kaj tiam vi havas la resto de via tabelo ke
fakte stokas ĉiujn ebloj de kio povis esti.
Do, ekzemple, kiel ĉe la supro vi havas
la unua kiu diras veraj aŭ falsa, jes aŭ ne, ĉi tiu estas vorto.
>> Kaj tiam vi havas 0 tra 26 de la literoj, ke vi povas stoki.
Se mi volis serĉi tie por vesperto, mi iras al la supro
kaj mi serĉos B. mi trovas B en mia tabelo, do mi scias, OK, estas B vorton?
B ne estas vorto, do tiel Mi devas teni serĉanta.
Mi iras de B, kaj mi rigardas al la montrilo ke B notas al
kaj mi vidas alian aron de informoj, la sama strukturo kiun ni havis antaŭe.
>> Kaj here-- ho, la sekva letero en [inaudible] estas A.
Do ni rigardu en tiu tabelo.
Ni trovas la oka valoro, kaj tiam ni rigardu vidi, ho,
hey, estas ke vorto, estas B-Al unu vorton?
Ĝi ne estas vorto.
Ni devas teni rigardante.
>> Kaj tiel do oni konsideras kie la montrilon de A punktoj,
kaj ĝi notas al alia maniero en kion ni havas pli valoro stokita.
Kaj fine, ni atingos B-Al-T, kiu estas vorto.
Do la sekvanta tempo vi aspektas, vi tuj
havi tiun ĉeko de, jes, ĉi Bulea funkcio estas vera.
Kaj tiel en la senco ni estas speco havi arbon kun tabeloj.
>> Tial do vi povas ia serĉu suben.
Anstataŭ hashing funkcio kaj asignanta valorojn per ligillisto,
Vi povas simple apliki trie ke sercxojn downwords.
Vere, vere komplikitaj aĵoj.
Ne facilas pensi ĉar mi ŝatas kracxi tiel multaj datumstrukturoj el
ĉe vi, sed faras ĉiu tipon de kompreni kiel la logiko de tio funkcias?
>> Bone, mojose.
Do B-Al-T, kaj tiam vi tuj serĉu.
La venontan fojon vi tuj vidi, ho, hej, ĝi estas vera,
tiele mi konas ĉi devas esti vorto.
>> Sama afero por zoo.
Do jen la afero nun, se ni volis serĉi bestoĝardeno, nun,
aktuale bestoĝardeno ne estas vorto en nia vortaro
ĉar, kiel vi infanoj povas vidi, la unua loko kiun ni havas Bulea
reveni vera estas fine de zoom.
Ni havas Z-ho-ho-M.
>> Kaj do ĉi tie, ni ne vere havas la vorto, zoo, en nia vortaro
ĉar tiu markobutono ne estas markita.
Do la komputilo ne scias ke bestoĝardeno estas vorto
ĉar la vojo kiun ni stokita, nur zoom tie
efektive havas Bulea valoro ke tio estis turnita vera.
Do se ni volas enmeti la vorto: zoo, en nia vortaro,
Kiel ni iras pri faranta tion?
Kion ni devas fari por certigi nian komputilo scias ke Z-ho-ho estas vorto
kaj ne la unua vorto estas Z-ho-ho-M?
>> Spektantaro: [inaudible]
>> ANDI PENG: Ĝuste, ni volas certigi ke ĉi
tie, ke Bulea valoro estas kontrolis ekstere ke ĝi estas vera.
Z-ho-ho, tiam ni tuj kontroli tion, tial ni scias precize, hej, bestoĝardeno estas vorto.
Mi tuj rakontos la komputilo ke ĝi estas vorto tiom
ke kiam la komputilo ĉekojn, ĝi scias ke bestoĝardeno estas vorto.
>> Ĉar memori ĉiuj ĉi tiuj datumoj strukturoj, ĝi estas tre facila por ni
diri, ho, vesperto estas vorto.
Zooparko estas vorto.
Zoom estas vorto.
Sed kiam vi konstruado ĝi, la komputilo havas nenian ideon.
>> Do vi devas diri ĝin precize en kio punkto estas tiu vorto?
Ĉe kiu punkto ĝi estas ne unu vorton?
Alian punkton mi bezonas serĉi aferojn,
kaj en kio punkto mi devas nun iri?
Ĉiu klara de tiu?
Malvarmeta.
>> Kaj tiel do venas la problemo de kiel estus ni
iri pri enmeto ion ke fakte ne ekzistas?
Do ni nur diros ni volas enmeti la vorto, bano, en nian trie.
Kiel vi uloj povas vidi kiel nuntempe ĉiuj ni havas nun estas B-Al-T,
kaj tiu nova datumstrukturo tie havis pint ke
montris nula ĉar ni supozas ke, ho, ekzistas neniu vortoj post B-Al-T,
kial ni devas teni havanta aferojn post ke T.
>> Sed la problemo ekestas se ni faras vin deziras havi vorton kiu venas post
la T.
Se vi havas banon, vi estas tuj volas H pravas.
Kaj tiel la vojon ni tuj faros kiu estas ni tuj krei apartan nodon.
Ni ne allot ajn kvanto de memoro por tiu nova tabelo,
kaj ni tuj reassign punteros.
>> Ni tuj asigni la H, Unue, tiu nula,
ni tuj forigi.
Ni tuj devas la H punkto suben.
Se ni vidas H, ni volas ĝin iri al ie alia.
>> En tie, ni povas tiam kontroli ekstere jes.
Se ni batis H post la T, ho, tiam ni scias ke tiu estas vorto.
La Buleaj tuj reveni vera.
Ĉiu klara de kiel tio okazis?
BONE.
>> Do esence, ĉiuj tiuj datumstrukturoj
ke ni trapasis hodiaŭ, mi havas trairinte ilin vere, vere rapide
kaj ne en multa detalo, kaj tio estas okej.
Unufoje vi komencas rompado kun ĝi, Vi estos
konservanta trako de kie ĉiuj punteros estas,
kio okazas en via datumstrukturoj, kaj tiel plu.
Ili estos tre utilaj, kaj ĝi estas ĝis vi
guys tute elkompreni kiel vi volas apliki aferojn.
>> Kaj tiel pset4, de 5-- ho, tio estas erara.
Pset5 estas fuŝo.
Kiel mi diris antaŭe, vi tuj, fojo denove, elŝuti fontkodon de ni.
Tie tuj estos tri ĉefaj aferoj vi estos elŝuto.
Vi elŝuti vortarojn, KERS, kaj tekstoj.
>> Ĉiuj tiuj aferoj estas estas ĉu vortarojn de vortoj
ke ni volas ke vi kontrolu aŭ testo de informo
ke ni deziras vin literumilo.
Kaj tial la vortaroj Ni donas vin iras
doni vin precizaj vortoj, ke ni volas vi stoki iel en maniero kiu estas
pli efika ol tabelo.
Kaj tiam la tekstoj estas tuj estos kio ni estas
demandante vin literumi kontroli por certiĝi ĉiuj vortoj estas veraj vortoj.
>> Kaj tiel la tri blokoj de programoj kiuj ni donos al vi
nomas dictionary.c, dictionary.h kaj speller.c.
Kaj tial ĉiuj dictionary.c faras estas kion vi demandis apliki.
Ĝi ŝarĝas vortoj.
Ĝi literumi ĉekojn ilin, kaj ĝi certigas ke ĉio estas enigita konvene.
>> diction.h estas nur biblioteko dosiero kiu deklaras ĉiuj tiuj funkcioj.
Kaj speller.c, ni tuj donas vin.
Vi ne bezonas modifi iuj ĝi.
Ĉiuj speller.c faras estas preni tiun, ŝarĝoj, kontrolas la rapidon de ĝi,
testas la etalono de kiel kiom rapide vi povos fari aferojn.
>> Estas literumanto.
Nur ne salaton kun ĝi, Sed faro certe vin komprenas kion ĝi faras.
Ni uzi funkcio nomita getrusage ke testas la rendimenton de via sorĉas
kontrolilo.
Ĉiuj faras estas esence testi la tempo de ĉio en via vortaro,
Tiel faro certe vi komprenas.
Penu ne salaton kun ĝi aŭ alia aĵoj ne kuras konvene.
>> Kaj la plejparton de tiu defio estas por you guys vere modifi dictionary.c.
Ni tuj donos al vi 140.000 vortojn en vortaro.
Ni tuj donos al vi tekston dosieron kiu havas tiujn vortojn,
kaj ni volas ke vi povos organizi ilin en hash tablo aŭ trie
ĉar kiam ni petas vin literumi check-- imagi se vi estas sorĉo
kontrolanta kiel Homero Odiseado.
Estas kiel tiu grandega, grandega provo.
>> Imagu se ĉiu unuopa vorto vi devis serĉi
tra tabelo de 140.000 valoroj.
Kiu portus ĉiam por via maŝino kuri.
Tial ni volas organizi niajn datumojn en pli efika datumstrukturoj
kiel hash tablo aŭ trie.
Kaj tiam vi uloj povas ia de kiam vi serĉu aliro
aferojn pli facile kaj pli rapide.
>> Kaj do atentu solvi kolizioj.
Vi tuj ricevos multajn vortoj de kiuj komenciĝas je A.
Vi tuj ricevos multajn vortojn ke komenco kun B. Ĝis vi
uloj kiel vi volas solvi ĝin.
Eble ekzistas pli efika hash funkcio
ol nur la unua litero de io, kaj tiel ke estas ĝis vi
uloj al speco de fari kion vi volas.
>> Eble vi deziras aldoni ĉiuj literoj kune.
Eble vi volas ŝatas fari strangajn aferojn ĝi rakontas la nombro de literoj,
ajn.
Ĝis vi uloj kiel vi volas fari.
Se vi volas fari hash tablo, se vi volas provi trie, tute dependas de vi.
Mi avertas vin antaŭ tempo ke la trie estas tipe iom pli malfacila
nur ĉar ekzistas multe pli punteros spuri.
Sed tute dependas de vi uloj.
Estas multe pli efika en plej kazoj.
Vi volas vere esti kapabla teni trako de ĉiuj viaj indikoj.
Kiel fari la saman aferon ke mi estis faranta tie.
Kiam vi provas enmeti valorojn en hash tablo aŭ forviŝi,
certiĝu ke vi estas vere konservanta trako
de kie ĉiu estas ĉar ĝi estas vere facila por se mi
provas enmeti kiel la vorto, andy.
Ni nur diras, ke estas reala vorto, la vorto, andy,
en giganta listo de A vortojn.
>> Se mi nur hazarde reassign montrilo malĝusta, oops,
tie iras la tuteco de la resto de mia ligillisto.
Nun la nura vorto mi havas estas andy, kaj nun
ĉiuj la aliaj vortoj en la vortaro perdiĝis.
Kaj do vi deziras fari certe vin sekvigi ĉiuj viaj indikoj
aŭ alie vi ricevos grandegaj problemoj en via kodo.
Desegni aferojn zorge paŝon post paŝo.
Ĝi faras ĝin tre pli facila elpensi.
>> Kaj fine, vi volas povi testi vian rendimenton de via programo
sur la granda tabulo.
Se vi infanoj prenas rigardas CS50 nun,
ni havos kion nomas la granda tabulo.
Estas la partituro folio de la plej rapida literumi kontrolanta fojojn tra ĉiuj de CS50
Ĝuste nun, mi kredas ke la supro kiel 10 tempoj mi pensas ok de ili estas bastono.
Ni vere volas vin infanoj bati nin.
>> Ni ĉiuj provis implementar la plej rapidan kodon kiel ebla.
Ni volas vin infanoj provi defii ni kaj efektivigi pli rapide ol ni ĉiuj
povas.
Kaj tiel tio estas vere la unua tempo ke ni estas
demandante vin infanoj fari pset ke vi povas vere fari en ajn metodo
vi volas.
>> Mi ĉiam diras, tiu estas pli parenca al reala-vivo solvo, ĉu ne?
Mi diras, hey, mi bezonas vin por fari tion.
Konstruu programo kiu faras tion por mi.
Ĉu ĝi tamen vi volas.
Mi nur scias ke mi volas fasti.
Tio estas via defio por tiu semajno.
Vi uloj, ni tuj doni al vi taskon.
Ni tuj donos al vi defion.
Kaj tiam ĝi estas ĝis vi infanoj tute simple elkalkuli
kio estas la plej rapida kaj plej efika maniero por efektivigi tion.
Yeah?
>> Spektantaro: Ĉu ni permesis al se volis esplori pli rapida manieroj
fari hash tabloj linio, ni povas fari ke kaj cite aliulaj kodo?
ANDI PENG: Jes, tute bone.
Do se vi infanoj legi la spec, ekzistas linio
en la spec kiu diras vin infanoj estas tute libera por priesplori hash
funkcioj sur kio estas iuj de la rapida kradaj funkcioj
kuri aĵojn tra kiel longe kiel vi citas ke kodo.
Do iuj personoj havas jam eltrovis rapidaj manieroj
fari sorĉas kontroliloj, de rapida manieroj de stoki informon.
Tute supren al vi knaboj, se vi volas nur prenu ke, dekstra?
Certiĝu vi citante.
La defio ĉi tie vere ke ni provas testi
estas certigi ke vi scias vian vojon ĉirkaŭ punteros.
Koncerne vin efektivigado la fakta hash funkcio
kaj venanta supre kun kiel la math fari tion,
vi uloj povas priesplori ajn metodoj rete vi uloj volas.
Yeah?
>> Spektantaro: Ĉu ni povas citi nur uzante la [inaudible]?
>> ANDI PENG: Yeah.
Vi povas simple, en via komento, vi povas citi kiel, oh,
prenita de Yada, Yada, Yada, hash funkcio.
Iu havas demandojn?
Ni efektive breezed tra sekcio hodiaŭ.
Mi estos supren tie al respondi demandojn ankaŭ.
>> Ankaŭ, kiel mi diris, oficejo horoj ĉinokte kaj morgaŭ.
La specifo ĉi semajno estas reale super facila kaj super mallonga legi.
Mi sugestus prenante rigardu, ĝuste legi tra la tuteco de ĝi.
>> Kaj Zamyla reale promenas vin tra ĉiu de la funkcioj
Vi devas efektivigi, kaj tiel ĝi estas tre tre klara kiel fari ĉion.
Ĝuste certigi ke vi estas konservanta trako de punteros.
Tio estas tre defia pset.
>> Ĝi ne estas defianta ĉar kiel, ho, la konceptoj estas tiel multe pli
malfacila, aŭ vi devas lerni tiel nova sintakso la vojon
ke vi faris por la lasta pset.
Ĉi pset estas malfacila ĉar Estas tiom multaj indikoj,
kaj tiam ĝi estas tre, tre facile tuj vi havas cimon en via kodo ne povos
trovi kie tiu cimo estas.
>> Kaj tiel kompleta kaj absoluta fido en vi uloj povi bati nia [inaudible]
literumojn.
Mi efektive ne havas skribita la mia ankoraŭ, sed mi volis skribi mian.
Do dum vi skribas via, mi skribos mia.
Mi tuj provos fari mia rapida ol la via.
Ni vidos kiu havas la plej rapida unu.
>> Kaj jes, mi vidos ĉiujn vi uloj tie marde.
Mi kuras speco kiel pset ateliero.
Ĉiuj la sekcioj ĉi semajno estas pset metiejoj,
tiel vi infanoj havas multajn ŝancojn por helpo, oficejo horoj kiel ĉiam,
kaj mi vere atendas senpacience leganta ĉiujn de viaj infanoj 'kodo.
Mi havas kvizojn ĉi tien se vi uloj volas veni akiri tiujn.
Tio estas ĉio.