>> [Music kucheza]
>> ANDI PENG: Karibu wiki 6 ya sehemu.
Sisi jitenga na kiwango chetu kifungu cha muda wa Jumanne
alasiri kwa hii nzuri kama Jumapili asubuhi.
Asante kwa kila mtu kwamba alijiunga nami leo, lakini kwa umakini,
raundi ya applause.
>> Hiyo ni juhudi pretty kubwa.
Mimi karibu hawakuwa hata kufanya hivyo up kwa wakati, lakini Ilikuwa ni sawa.
Hivyo najua kwamba nyote have just alifanya hivyo kwa jaribio.
Awali ya yote, kuwakaribisha kwa upande wa kwamba flip.
>> Pili, tutaweza kuzungumzia suala hilo.
Tutaweza majadiliano juu ya jaribio.
Tutaweza majadiliano juu ya jinsi unafanya darasani.
Wewe utakuwa na faini.
Nina Quizzes yako kwa wewe mwishoni mwa hapa,
hivyo kama wewe guys wanataka kuchukua a ukiangalia hiyo, kabisa faini.
>> Hivyo haraka kabla hatujaanza, ajenda ya leo ni kama ifuatavyo.
Kama unaweza kuona, tuko kurusha kimsingi haraka
kupitia rundo zima la miundo data kweli, kweli, kweli haraka.
Hivyo kama hizo, haitakuwa super shirikishi leo.
Ni itabidi tu kuwa mimi aina ya kelele mambo ambayo wewe, na kama mimi kuwavurugia wewe,
kama mimi nina kwenda kwa haraka sana, napenda kujua.
Wao ni takwimu tu mbalimbali miundo, na kama sehemu
ya pset yako kwa hii wiki ijayo, utasikia
kuulizwa kutekeleza mmoja wao, labda wawili wa them-- wawili kati yao
katika pset yako.
OK, hivyo mimi nina kwenda tu kwa kuanza na baadhi ya matangazo.
Tutaweza kwenda juu ya mwingi na foleni zaidi katika kina kuliko yale tulivyofanya kabla jaribio.
Tutaweza kwenda juu wanaohusishwa orodha tena, kwa mara nyingine tena,
zaidi katika kina kuliko yale tulikuwa na kabla ya jaribio.
Na kisha tutaweza majadiliano juu hash meza, miti na inajaribu, ambayo
wote ni pretty muhimu kwa pset yako.
Na kisha tutaweza kwenda juu baadhi tips msaada kwa pset5.
>> OK, hivyo jaribio 0.
Wastani ulikuwa 58%.
Ilikuwa ni ndogo sana, na hivyo nyie wote alifanya sana, vizuri sana kwa mujibu
na kwamba.
>> Pretty sana, utawala wa kidole gumba ni kama wewe ni ndani ya kupotoka kiwango cha wastani
hasa kwa vile tuko katika chini kifungu cha comfy, wewe ni kabisa faini.
Wewe ni juu ya kufuatilia.
Maisha ni mazuri.
>> Najua ni inatisha kufikiri kwamba I got kama 40% juu ya jaribio hili.
Mimi nina kwenda kushindwa darasa hili.
Mimi ahadi yenu, wewe si kwenda kushindwa darasani.
Wewe ni kabisa faini.
>> Kwa wale ambao got juu ya maana, ya kuvutia, kuvutia,
kama, kwa umakini vizuri.
Mimi kuwa nao pamoja nami.
Kujisikia huru kuja kupata yao mwishoni mwa sehemu.
Napenda kujua kama una masuala, maswali pamoja nao.
Kama sisi kuongeza alama yako makosa, hebu kujua.
>> OK, hivyo pset5, hii ni kweli wiki weird kwa Yale kwa maana ya
kwamba pset yetu ni kutokana Jumatano saa sita mchana ikiwa ni pamoja na
siku marehemu, hivyo ni kweli kinadharia kutokana Jumanne saa sita mchana.
Pengine hakuna mtu kumaliza katika Jumanne saa sita mchana.
Hiyo ni kabisa faini.
Tunakwenda kuwa na masaa ya ofisi usiku wa leo ikiwa ni pamoja na Jumatatu usiku.
Na wote wa sehemu ya wiki hii itakuwa kweli kugeuzwa kuwa warsha,
ili kujisikia huru na pop katika sehemu yoyote unataka,
na wao utakuwa aina ya mini-pset warsha kwa ajili ya kusaidia juu ya jambo hilo.
Hivyo kama hizo, hii ni sehemu tu ambapo sisi ni kufundisha nyenzo.
Sehemu nyingine yote itakuwa kulenga peke juu msaada kwa pset.
Yeah?
>> Watazamaji: ni masaa ya ofisi wapi?
>> ANDI PENG: Ofisi ya masaa tonight-- loo, swali zuri.
Nadhani masaa ya ofisi usiku wa leo ni katika Teal au huru.
Kama wewe kuangalia online CS50 na wewe kwenda masaa ya ofisi,
kuwe na ratiba kwamba atakwambia ambapo wote ni.
>> Najua ama usiku wa leo au kesho ni teal,
na nadhani tuwe na commons kwa usiku mmoja.
Sina uhakika.
Nzuri swali.
Angalia juu ya CS50.
>> Baridi, maswali yoyote kuhusu ratiba kwa ajili ya pili kama siku tatu?
Mimi ahadi nyie kama Daudi Alisema, hii ni juu ya kilima.
Nyie ni karibu na hapo.
Tu siku tatu zaidi.
Kufika huko, na kisha tutaweza wote kuja chini.
Kutakuwa na nzuri CS-bure mapumziko.
Tutaweza kurudi.
Tutaweza kupiga mbizi katika mtandao programu na maendeleo,
mambo ambayo ni furaha sana ikilinganishwa kwa baadhi ya psets mengine.
Na utakuwa baridi, na tutaweza kuwa na kura ya kujifurahisha.
Kutakuwa na pipi zaidi.
Pole kwa pipi.
I forgot pipi.
Ilikuwa ni mbaya asubuhi.
Hivyo nyie ni karibu na hapo, na mimi nina kweli fahari ya nyie.
>> OK, hivyo mwingi.
Aliyependa swali kuhusu Jack na mavazi yake juu ya jaribio?
Hakuna mtu?
OK, hiyo ni nzuri.
>> Hivyo kimsingi kama unaweza picha Jack, hii guy hapa,
anapenda kuchukua mavazi nje ya juu ya mnara,
na kuiweka nyuma kwenye stack baada ya kufanyika.
Hivyo kwa njia hii, yeye kamwe inaonekana kuwa kupata
chini ya stack katika mavazi yake.
Hivyo hii aina ya inaelezea muundo wa msingi data
jinsi stack unatekelezwa.
>> Kimsingi, fikiria stack kama stack yoyote ya vitu
ambapo kuweka mambo kwenye kilele, na basi pop yao nje kutoka juu.
Hivyo LIFO ni kifupi sisi kama kwa use-- Mwisho Katika, Kati ya kwanza.
Na hivyo mwisho katika kilele cha stack ni moja ya kwanza kwamba inakuja nje.
Na hivyo vipindi viwili sisi kama kujiunga
na walioitwa kushinikiza na pop.
Wakati kushinikiza kitu kwenye stack, na pop ni nyuma juu.
>> Na hivyo mimi nadhani hii ni aina ya abstract dhana kwa wale
ambao wanataka kuona kama halisi ya utekelezaji wa hii
katika ulimwengu wa kweli.
Ni wangapi wenu wameandika insha labda kama saa moja kabla ni kutokana,
na wewe ajali ilifutwa mkubwa chunk ya hayo, kama ajali?
Na kisha nini kudhibiti kufanya tunatumia kwa kuiweka nyuma?
Kudhibiti-Z, yeah?
Kudhibiti-Z, hivyo kiasi cha mara kwamba Kudhibiti-Z ana kuokolewa maisha yangu,
imekuokoa punda wangu, kila wakati hiyo ni kutekelezwa kupitia stack.
>> Kimsingi taarifa zote hiyo ni juu ya Neno hati yako,
anapata kusukuma na popped katika mapenzi.
Na hivyo kimsingi wakati wowote kufuta kitu chochote, wewe pop ni nyuma juu.
Na kisha kama unahitaji yake nyuma, wewe kuiondoa, ambayo ni nini Kudhibiti-C gani.
Na dunia kazi hivyo kweli muundo wa jinsi rahisi data
inaweza kusaidia na maisha yako ya kila siku.
>> Hivyo struct ni njia ambayo sisi kweli kujenga stack.
Sisi aina kufafanua struct, na kisha sisi kuiita stack chini.
Na ndani ya stack, tuna vigezo mbili
tuweze kimsingi kuendesha, hivyo tuna char masharti nyota uwezo.
>> Yote hayo ni kufanya ni kujenga safu
tuweze kuhifadhi chochote unataka ambayo tunaweza kuamua uwezo wake.
Uwezo Je, tu kiasi max ya vitu tunaweza kuweka katika safu hii.
int kawaida ni kukabiliana na kwamba anaendelea wimbo wa vitu ni wangapi kwa sasa
katika stack.
Hivyo basi tunaweza kuweka wimbo wa, A, wote jinsi kubwa stack halisi ni,
na, B, kiasi gani ya kwamba mkusanyiko sisi kujazwa kwa sababu hatutaki
kufurika juu ya nini uwezo wetu ni.
>> Hivyo kwa mfano, hii lovely swali lilikuwa juu ya jaribio lako.
Kimsingi ni jinsi gani sisi kushinikiza kwenye juu ya stack.
Pretty rahisi.
Kama ukiangalia hiyo, tutaweza kutembea kwa njia hii.
Kama [inaudible] size-- kumbuka, wakati wowote
wanataka kupata yoyote parameter ndani ya struct,
kufanya jina la struct.parameter.
>> Katika kesi hiyo, s ni jina la stack yetu.
Tunataka kupata ukubwa yake, hivyo tunafanya s.size.
Hivyo muda mrefu kama kawaida si sawa na uwezo au kwa muda mrefu
kama ni chini ya uwezo, ama ingekuwa kazi hapa.
>> Unataka kupata ndani ya ya stack yako, hivyo s.strings,
na wewe ni kwenda kuweka kwamba idadi mpya kwamba unataka kuingiza ndani huko.
Hebu tu kusema sisi atataka kuingiza int n kwenye stack,
tunaweza kufanya s.strings, mabano, s.size sawa na n.
Kwa sababu ukubwa ni mahali ambapo sisi sasa ni katika mkusanyiko
kama sisi ni kwenda kushinikiza juu, sisi tu kupata
popote ukubwa ni, ukamilifu wa sasa wa stack,
na sisi kushinikiza int n kwenye hilo.
Na kisha tunataka kuhakikisha kwamba tuko pia incrementing ukubwa wa n,
ili tuweze kuweka wimbo wa tumekuwa aliongeza jambo ziada kwa stack.
Sasa tuna ukubwa kubwa zaidi.
Je, hii hapa mantiki kila mtu, jinsi mantiki kazi?
Ilikuwa ni aina ya haraka.
Watazamaji: Je, unaweza kwenda juu s.stringss.strings [s.size] tena?
ANDI PENG: Hakika, hivyo nini s.size sasa kutupa?
Watazamaji: Ni kawaida sasa.
ANDI PENG: Hasa, hivyo sasa ripoti kwamba ukubwa yetu ni katika,
na hivyo tunataka kuweka integer mpya kwamba tunataka kuingiza ndani s.size.
Je, hiyo mantiki?
Kwa sababu s.strings, wote ni ni jina la safu.
Wote ni kupata ni safu ndani ya struct yetu,
na hivyo kama tunataka mahali n ndani ya kwamba ripoti,
tunaweza tu kupata hiyo kutumia mabano s.size.
Baridi.
>> Sawa, pop, mimi pseudocode nje kwa nyie, lakini dhana sawa.
Je, hiyo mantiki?
Kama ukubwa ni mkubwa kuliko sifuri, basi
tunajua kwamba unataka kuchukua kitu nje kwa sababu kama ukubwa sio
mkubwa kuliko sifuri, basi hawana kitu katika stack.
>> Hivyo tu wanataka nitafanya kanuni hii, inaweza tu
pop kama kuna kitu pop.
Hivyo kama kawaida, ni mkubwa kuliko 0, sisi bala ukubwa.
Sisi pungufu ukubwa na kisha kurudi chochote ni ndani yake kwa sababu
kwa popping, tunataka upatikanaji chochote ni kuhifadhiwa
katika ripoti ya juu ya stack.
Kila kitu mantiki?
Kama mimi alifanya nyie kuandika hii nje, ingekuwa nyie kuwa na uwezo wa kuandika ni nje?
Sawa, wewe guys unaweza kucheza karibu na hiyo.
Hakuna wasiwasi kama huna kupata.
Hatuna muda wa kanuni nje leo kwa sababu tumekuwa
got mengi ya miundo haya kupitia, lakini kimsingi
pseudocode, sana, ni sawa na kushinikiza.
Tu kufuata pamoja mantiki.
Kuhakikisha wewe ni kupata yote sifa za struct yako kwa usahihi.
Yeah?
>> Watazamaji: Je, slides hizi na jambo hili zima kuwa juu leo-ish?
ANDI PENG: Daima, yep.
Mimi nina kwenda kujaribu kuweka huu juu kama saa baada.
Mimi itabidi email Daudi, Daudi watajaribu kuiweka juu kama saa baada ya hii.
>> OK, hivyo basi sisi kuhamia katika hii nyingine nzuri muundo wa data aitwaye foleni.
Kama nyie unaweza kuona hapa, foleni, kwa Waingereza miongoni mwetu,
yote ni ni mstari.
Hivyo kinyume na kile unafikiri stack ni,
foleni ni nini hasa kifikra unadhani ni.
Ni uliofanyika kwa sheria za FIFO, ambayo ni ya kwanza katika, Kati ya kwanza.
Kama uko kwanza moja katika mstari, wewe ni
moja ya kwanza kwamba hutoka nje ya mstari.
>> Hivyo kile sisi kama kuwaita hii ni dequeueing na enqueueing.
Kama tunataka kuongeza kitu kwa foleni yetu, sisi enqueue.
Kama tunataka dequeue, au kuchukua kitu mbali, sisi dequeue.
>> Hivyo huo maana kwamba sisi ni aina ya kujenga mambo fasta ukubwa kwamba sisi
wanaweza kuhifadhi baadhi ya mambo, lakini tunaweza pia
mabadiliko ambapo sisi ni kuweka vigezo ndani yao
kulingana na aina gani ya utendaji tunataka.
Hivyo mwingi, tulitaka mwisho moja, N niwe wa kwanza moja nje.
Foleni ni tunataka jambo la kwanza katika kuwa jambo la kwanza nje.
>> Hivyo struct aina kufafanua, kama unaweza kuona,
ni kidogo tofauti kutokana na kile stack alikuwa
kwa sababu si tu kufanya tuna kuweka wimbo wa ambapo ukubwa kwa sasa ni,
sisi pia wanataka kuweka wimbo wa kichwa kama vile ambapo sisi sasa ni.
Hivyo nadhani ni rahisi kama mimi kuteka hii up.
Basi hebu fikiria sisi tumepewa foleni, hivyo hebu sema kichwa ni haki hapa.
Mkuu wa mstari, hebu tu kusema kwamba kwa sasa kuna,
na tunataka Insert kitu katika foleni.
Mimi nina kwenda kuwaita ukubwa kimsingi ni kitu kimoja kama mkia,
Mwishoni mwa popote foleni yako ni.
Hebu tu kusema ukubwa ni haki hapa.
>> Hivyo ni jinsi gani kuchukuliwa kwa moja kuingiza kitu katika foleni?
Nini ripoti tunataka kuweka ambapo tunataka kuingiza ndani.
Kama hii ni mwanzo wa yako foleni na hii ni mwisho wake
au ukubwa wa jambo hilo, ambapo kufanya sisi unataka kuongeza kitu baada ya hapo?
>> Watazamaji: [inaudible]
ANDI PENG: Hasa, unataka kuongeza ni kulingana na umeandika yake.
Aidha huu ni tupu au kwamba ni tupu.
Kwa hiyo unataka kuongeza kuwa pengine hapa kwa sababu kama ukubwa is--
kama haya yote ni kamili, unataka kuongeza kuwa haki hapa, hivi?
>> Na hivyo ndiyo, wakati sana, sana rahisi, si mara zote kabisa sahihi
kwa sababu Tofauti kubwa kati ya foleni na stack
ni kwamba foleni Unaweza kweli kuwa manipulated
ili mabadiliko kichwa kulingana na pale unataka
mwanzo wa cue yako ya kuanza.
Na matokeo yake, mkia yako Pia inaenda kubadilika.
Na hivyo tuangalie kanuni hii hivi sasa.
Kama nyie waliulizwa pia kwa kuandika juu ya jaribio, enqueue.
Labda tutaweza majadiliano kupitia kwa nini Jibu lilikuwa ni kitu gani.
>> Sikuweza kabisa walionao mstari huu kwenye moja, lakini kimsingi kipande hii ya kificho
lazima juu ya mstari mmoja.
Kutumia kama sekunde 30.
Kuangalia, na kuona kwa nini hii ni njia ya kuwa ni.
>> Sana, ni sawa struct, sana, sana muundo sawa kama awali
stack isipokuwa kwa labda mstari mmoja wa kanuni.
Na kwamba line moja ya kanuni huamua utendaji.
Na ni kweli differentiates foleni kutoka stack.
>> Mtu yeyote wanataka kuchukua kumchoma katika kueleza kwa nini umefanya
got jambo hili ngumu katika hapa?
Tunaona kurudi kwa wetu ajabu rafiki modulus.
Kama nyie hivi karibuni kuja kutambua katika programu,
karibu wakati wowote unahitaji kitu kufungia kitu chochote,
modulus ni kwenda kuwa njia ya kufanya hivyo.
Hivyo kujua kwamba, haina mtu yeyote wanataka kujaribu kueleza kuwa mstari wa kanuni?
Naam, majibu yote ni kukubalika na kuwakaribisha.
Watazamaji: Je, wewe ni kuzungumza na mimi?
ANDI PENG: Naam.
Watazamaji: Oh, hakuna pole.
ANDI PENG: Sawa, hivyo hebu kutembea kwa njia ya kanuni hii.
Hivyo wakati wewe ni kujaribu kuongeza kitu kwenye foleni,
katika kesi nzuri ya kuwa kichwa hutokea kuwa na haki hapa, ni rahisi sana kwa ajili yetu
tu kwenda hadi mwisho kuingiza kitu, sawa?
Lakini hoja nzima ya foleni ni kuwa kichwa Unaweza kweli dynamically
mabadiliko kulingana na pale sisi wanataka kuanza kwa q yetu kuwa,
na kama vile, mkia Pia inaenda kubadilika.
>> Na hivyo kufikiria kwamba hii haikuwa foleni, lakini badala ya hii ilikuwa foleni.
Hebu sema kichwa ni haki hapa.
Hebu sema foleni yetu inaonekana kama hii.
Kama tulitaka kuhama ambapo mwanzo wa mstari ni,
hebu sema sisi kubadilishwa kichwa njia hii na ukubwa hapa.
>> Sasa tunataka kuongeza kitu kwa foleni hii, lakini kama wewe guys unaweza kuona,
siyo rahisi ili tu kuongeza chochote ni baada ukubwa
kwa sababu kisha sisi kukimbia nje ya mipaka ya safu yetu halisi.
Ambapo tunataka kweli kuongeza ni hapa.
Hiyo ni uzuri wa foleni ni kwamba kwa sisi, kuibua
Inaonekana kama mstari unaendelea kama hii, lakini wakati kuhifadhiwa katika muundo data,
wao kuwapa kama kama mzunguko.
Ni aina ya Wraps kuzunguka mbele kwa njia hiyo hiyo
kuwa mstari unaweza pia kufuta karibu kutegemea popote
wanataka mwanzo wa mstari kuwa.
Na hivyo kama sisi kuchukua kuangalia chini hapa, hebu
kusema sisi alitaka kujenga kazi kuitwa enqueue.
Tulitaka kuongeza int n ndani ya kwamba q.
Kama q.size q-- tutaweza wito kwamba takwimu zetu structure-- ikiwa queue.size yetu haina
sawa na uwezo au kama ni chini ya uwezo,
q.strings ni safu ndani ya q wetu.
Tunakwenda kuweka kuwa sawa na q.heads,
ambayo ni haki hapa, pamoja na q.size modulus na uwezo, ambayo
wrap sisi nyuma kuzunguka hapa.
>> Hivyo katika mfano huu, ripoti ya kichwa ni 1, sawa?
Ripoti ya ukubwa ni 0, 1, 2, 3, 4.
Hivyo tunaweza kufanya 1 plus 4 modulus na uwezo wetu ambao ni 5.
Je, hiyo kutupa?
Ni nini kwamba ripoti hutoka nje ya hili?
>> Watazamaji: 0.
>> ANDI PENG: 0, ambayo hutokea kwa kuwa hapa hapa,
na hivyo tunataka kuwa na uwezo kuingiza ndani ya haki hapa.
Na hivyo swala hilo hapa aina ya kazi tu kwa idadi yoyote
kulingana na pale yako kichwa na ukubwa wako ni.
Kama unajua nini wale mambo ni, unajua
hasa ambapo unataka kuingiza chochote ni baada ya foleni yako.
Je, hiyo mantiki kwa kila mtu?
>> Najua aina ya ubongo teaser hasa kwa vile hii
alikuja katika Baada ya jaribio lako.
Lakini pengine kila mtu sasa unaweza kuelewa
kwa nini ufumbuzi huu au huu kazi ni njia ambayo ni.
Mtu yeyote bit wazi juu ya hilo?
SAWA.
>> Na hivyo sasa, kama wewe alitaka dequeue, hii
Hapa ndipo kichwa yetu itakuwa kuhama kwa sababu kama tulikuwa dequeue,
hatuwezi kuchukua mbali mwisho wa q.
Tunataka kuchukua mbali kichwa, sawa?
Hivyo kama matokeo, mkuu ni kwenda na mabadiliko, na kwamba ni kwa nini wakati wewe enqueue,
nimepata kuweka wimbo wa ambapo kichwa yako na ukubwa yako
ni kuwa na uwezo wa kuingiza ndani ya msimamo sahihi.
>> Na hivyo wakati wewe dequeue, Mimi pia pseudocode nje.
Kujisikia huru na kama unataka kujaribu coding hii nje.
Unataka kusonga kichwa, sawa?
Kama nilitaka dequeue, mimi ingekuwa hoja kichwa juu.
Hii itakuwa kichwa.
>> Na ukubwa wetu wa sasa ingekuwa Ondoa kwa sababu sisi tena
na mambo manne katika safu.
Sisi tu tatu, na kisha tunataka kurudi chochote alikuwa kuhifadhiwa ndani ya
ya kichwa kwa sababu tunataka kuchukua hii thamani nje hivyo sana sawa na stack.
Tu wewe ni kuchukua kutoka sehemu mbalimbali,
na una reassign pointer yako mahali tofauti kama matokeo.
Kimantiki, kila mtu kufuata?
Kubwa.
>> OK, hivyo sisi ni kwenda kuzungumza kidogo zaidi katika kina kuhusu orodha wanaohusishwa
kwa sababu wao utakuwa sana, muhimu sana kwa wewe katika mwendo wa wiki hii
psets.
Orodha wanaohusishwa, kama nyie unaweza kukumbuka, kila wao ni
ni nodes kuwa ni nodes ya baadhi ya maadili ya wote thamani na pointer
ambazo zinatumika pamoja na kuyatumia hizo.
Na hivyo struct juu ya jinsi sisi kujenga nodi hapa ni sisi
kuwa int n, ambayo ni chochote thamani katika kuhifadhi au kamba n
au chochote unataka simu yake, char nyota n.
Nyota nodi struct, ambayo ni pointer kwamba unataka kuwa katika kila nodi,
wewe ni kwenda na kwamba pointer hatua kuelekea ijayo.
Itabidi kichwa ya orodha wanaohusishwa hiyo ni
kwenda kwa uhakika na maeneo mengine ya maadili kadhalika na kadhalika
mpaka hatimaye kufikia mwisho.
Na node hii ya mwisho ni kwenda kuwa na pointer.
Ni kwenda kwa uhakika na null, na kwamba wakati
unajua umefanya kugonga mwisho wa orodha yako wanaohusishwa
ni wakati pointer yako ya mwisho haina uhakika na kitu chochote.
>> Hivyo sisi ni kwenda kidogo zaidi katika kina kuhusu jinsi moja ingekuwa uwezekano
kutafuta orodha wanaohusishwa.
Kumbuka ni nini baadhi ya hasara ya orodha wanaohusishwa
aya safu kuhusu upekuzi.
Safu unaweza search binary, lakini kwa nini hawawezi kufanya hivyo katika orodha wanaohusishwa?
>> Watazamaji: Kwa sababu wao ni wote kushikamana, lakini huna kabisa kujua wapi
[Inaudible].
>> ANDI PENG: Yeah, kwa uhakika hivyo kumbuka kwamba uzuri wa safu
alikuwa na ukweli kwamba tulikuwa na random kupata kumbukumbu ambapo
kama nilitaka thamani kutoka ripoti sita, sikuweza kusema tu ripoti sita,
nipe thamani hiyo.
Na hiyo ndiyo sababu arrays ni yamepangwa katika nafasi contiguous ya kumbukumbu
katika sehemu moja, ambapo aina ya orodha wanaohusishwa
ni nasibu Kukifuatiwa pande zote, na njia pekee unaweza kupata moja
Ni kwa njia ya pointer kwamba anaelezea pepe ya ambapo kwamba nodi ijayo ni.
>> Na hivyo matokeo yake, njia pekee kutafuta njia orodha wanaohusishwa
ni kutafuta linear.
Kwa sababu mimi si hasa kujua ambapo 12 thamani katika orodha wanaohusishwa ni,
Nina traverse ukamilifu ya kwamba wanaohusishwa orodha moja
kwa moja kutoka kichwani hadi nodi kwanza, nodi pili, kwa nodi ya tatu,
njia yote chini mpaka mimi hatimaye kupata ambapo kwamba nodi mimi nina kuangalia kwa ni.
Na hivyo kwa maana hii, kutafuta juu ya orodha wanaohusishwa ni daima n.
Ni siku zote n.
Ni siku zote katika muda linear.
>> Na hivyo kificho katika ambayo sisi kutekeleza hili, na hii
ni kidogo mpya kwa nyie tangu guys si kweli aliyesema kuhusu au milele
kuyatumia kuonekana katika namna ya kutafuta njia ya kuyatumia,
hivyo tutaweza kutembea kwa njia ya huu sana, polepole sana.
Hivyo bool utafutaji, haki, hebu fikiria tunataka
kujenga kazi kuitwa search kwamba anarudi kweli
kama wewe kupatikana thamani ndani ya wanaohusishwa orodha, na kuirudisha uongo vinginevyo.
Orodha nodi nyota ni sasa tu pointer
kwa bidhaa ya kwanza katika orodha yako wanaohusishwa.
int n ni thamani kwamba wewe ni kwa ajili ya kutafuta katika orodha hiyo.
>> Hivyo nyota nodi pointer sawa na orodha.
Hiyo ina maana sisi ni kuweka na kujenga pointer
kwa kuwa nodi kwanza ndani ya orodha.
Kila mtu na mimi?
Hivyo kama sisi walikuwa kwenda huku nyuma, mimi ingekuwa
initialized pointer kwamba pointi kwa mkuu wa chochote orodha hiyo ni.
>> Na kisha mara moja kupata chini hapa, wakati pointer haina sawa null,
hivyo kwamba ni kitanzi ambayo sisi ni kwenda kuwa hatimaye apitaye
wengine wa orodha yetu kwa sababu gani hutokea wakati pointer sawa null?
Tunajua kwamba sisi have--
>> Watazamaji: [inaudible]
>> ANDI PENG: Hasa, hivyo tunajua kwamba tumekuwa kufikiwa mwisho wa orodha, sawa?
Kama kwenda nyuma hapa, kila nodi lazima akizungumzia nodi mwingine
na kadhalika na kadhalika mpaka hit hatimaye
mkia wa orodha yako wanaohusishwa, ambayo ina pointer kwamba tu
haina uhakika popote nyingine zaidi hapana.
Na hivyo kimsingi kujua kwamba orodha yako bado ni pale juu
mpaka pointer haina sawa null sababu mara moja ni sawa null,
unajua kwamba hakuna mambo zaidi.
>> Hivyo kwamba ni kitanzi ambayo tuko kwenda na kutafuta halisi.
Na kama pointer unaona aina hiyo ya mshale kazi huko?
Hivyo kama pointi pointer n, ikiwa pointer katika n sawa sawa na n,
hivyo kwamba maana kwamba kama pointer kwamba wewe ni
kwa ajili ya kutafuta juu ya mwisho wa kila nodi ni kweli sawa na thamani
wewe kutafuta, basi unataka kurudi kweli.
Hivyo kimsingi, kama wewe ni katika nodi kwamba ina thamani kwamba wewe ni kuangalia kwa,
unajua kwamba tumekuwa uwezo wa mafanikio kutafuta.
>> Vinginevyo, unataka kuweka pointer yako nodi ijayo.
Hilo ndilo kwamba mstari hapa ni kufanya.
Pointer sawa na pointer ijayo.
Kila mtu kuona ni jinsi hiyo kazi?
>> Na kimsingi wewe ni kwenda tu traverse ukamilifu wa orodha,
upya pointer yako kila wakati mpaka wewe hatimaye kugonga mwisho wa orodha.
Na unajua kwamba hakuna nodes zaidi kutafuta njia,
na kisha unaweza kurudi uongo kwa sababu unajua kwamba, loo, vizuri,
kama nimekuwa na uwezo wa kutafuta kupitia ukamilifu wa orodha.
Kama katika mfano huu, kama nilitaka kutafuta thamani ya 10,
na mimi kuanza kichwani na Mimi kutafuta njia yote chini,
na mimi hatimaye got hii, ambayo pointer kwamba pointi kwa null,
Najua kwamba, crap, mimi nadhani 10 sio katika orodha hii kwa sababu sikuweza kupata hiyo.
Na mimi nina mwishoni mwa orodha.
Na katika kesi ambayo unajua Mimi nina kwenda na kurudi uongo.
>> Hebu kuwa loweka katika kwa muda kidogo.
Hii itakuwa pretty muhimu kwa pset yako.
Mantiki yake ni rahisi sana, labda syntactically tu kutekeleza hayo.
Nyie wanataka kufanya kuhakikisha kwamba wewe kuelewa.
Baridi.
>> OK, hivyo ni jinsi sisi itakuwa kuingiza nodes, kulia,
ndani ya orodha kwa sababu kumbuka nini ni nini faida
ya kuwa na orodha wanaohusishwa dhidi safu katika suala la kuhifadhi?
>> Watazamaji: Ni nguvu, hivyo ni rahisi to--
>> ANDI PENG: Hasa, hivyo ni nguvu, ambayo
ina maana kwamba inaweza kupanua na kuogopa kulingana na mahitaji ya mtumiaji.
Na hivyo, kwa maana hii, hatuna haja kupoteza kumbukumbu ya lazima kwa sababu mimi
kama sijui wangapi maadili nataka dukani, haina mantiki kwa ajili yangu
kujenga safu kwa sababu kama nataka kuhifadhi maadili 10
na mimi kuunda safu ya 1000, hiyo ni mengi ya kupita kumbukumbu, uliopangwa.
Hiyo ni kwa nini tunataka kutumia wanaohusishwa orodha kuweza dynamically
mabadiliko au kuogopa ukubwa yetu.
>> Na hivyo kwamba inafanya kuingizwa kidogo ngumu zaidi.
Tangu hatuwezi nasibu kupata mambo njia ambayo tunataka ya safu.
Kama mimi nataka kuingiza kipengele ndani ya saba ripoti,
Mimi tu hawezi kuingiza ndani ya saba ripoti.
Katika orodha wanaohusishwa, haina kabisa kazi kwa urahisi,
na hivyo kama sisi alitaka kuingiza moja hapa katika orodha wanaohusishwa,
kuibua, ni rahisi sana kuona.
Sisi tu wanataka kuingiza haki pale, haki katika mwanzo wa orodha,
haki baada ya kichwa.
>> Lakini njia ambayo tuna reassign kuyatumia ni kidogo convoluted
au, kifikra, inafanya hisia, lakini unataka kuhakikisha kwamba una hiyo
kabisa chini kwa sababu Jambo la mwisho unataka
ni kwa reassign pointer njia ambayo sisi ni kufanya hapa.
Kama dereference pointer kutoka kichwa na 1,
kisha wote wa the ghafla mapumziko ya orodha yako wanaohusishwa
ni kupotea kwa sababu una si kweli kuumba kitu chochote muda.
Hiyo alisema kwa 2.
Kama reassign pointer, kisha mapumziko ya orodha yako ni kupotea kabisa.
Kwa hiyo unataka kuwa mwangalifu sana hapa
kwa kuwapa kwanza pointer kutoka chochote
wanataka kuingiza ndani popote unataka, na kisha
Unaweza dereference mapumziko ya orodha yako.
>> Hivyo hii inatumika kwa popote wewe ni kujaribu kuingiza ndani.
Kama unataka kuingiza katika kichwa, kama unataka kujibu hapa,
kama unataka kuingiza katika mwisho, vizuri, mwisho mimi
nadhani wewe ungekuwa tu hawana pointer, lakini wewe
unataka kuhakikisha kwamba huna kupoteza mapumziko ya orodha yako.
Siku zote unataka kuhakikisha nodi yako mpya ni akizungumzia
kuelekea chochote wanataka kuingiza ndani,
na kisha unaweza kuongeza chaining juu.
Kila mtu wazi?
>> Hii ni kwenda kuwa moja ya masuala halisi.
Moja ya masuala makubwa zaidi wewe ni kwenda na juu ya pset yako
ni kwamba wewe ni kwenda kujaribu kujenga orodha wanaohusishwa na mambo kuingiza
lakini basi tu kupoteza mapumziko ya orodha yako wanaohusishwa.
Na wewe ni kwenda kuwa kama mimi sijui ni kwa nini hii inajitokeza?
Na ni maumivu kupitia na kutafuta wote wa kuyatumia yako.
>> Na Mimi kuhakikisha juu ya pset hii, kuandika na kuchora nodi hiyo nje
itakuwa sana, sana.
Hivyo unaweza kabisa kuweka wimbo wapi kuyatumia yako yote ni,
nini kinaendelea vibaya, ambapo nodes yako yote ni,
nini unahitaji kufanya ili kupata au kuingiza au kufuta au yeyote kati yao.
Kila mtu mzuri na kwamba?
Baridi.
>> Hivyo kama sisi alitaka kuangalia kanuni?
Oh, mimi sijui kama sisi Unaweza kuona the-- OK, hivyo
juu ya yote ni ni kazi aitwaye kuingiza ambapo tunataka
kuingiza int n ndani ya orodha wanaohusishwa.
Tunakwenda kutembea kwa njia hii.
Ni mengi ya kificho, mengi ya syntax mpya.
Tutaweza kuwa sawa.
>> Hivyo hadi saa juu, wakati wowote tunataka kujenga kitu chochote
tunahitaji nini cha kufanya, hasa kama wewe wanataka kuwa na si kuhifadhiwa kwenye mkusanyiko
lakini katika chungu?
Sisi kwenda kwa malloc, sawa?
Hivyo sisi ni kwenda kujenga pointer.
Node, pointer, sawa mapya malloc ukubwa wa nodi
kwa sababu tunataka kuwa nodi kuundwa.
Tunataka kiasi cha kumbukumbu kwamba nodi unachukua
kwa kuwa kura kwa uundwaji wa nodi mpya.
>> Na kisha tunakwenda kuangalia kwa kuona kama sawa mapya ni sawa na null.
Kumbuka kile sisi alisema?
Chochote malloc, kile ambacho ni lazima daima kufanya?
Lazima daima kuangalia kuona iwapo au kuwa ni batili.
>> Kwa mfano, kama uendeshaji wako mfumo alikuwa kabisa kamili,
kama alikuwa na kumbukumbu tena katika zote na wewe kujaribu malloc,
ingekuwa kurudi null kwa ajili yenu.
Na hivyo kama wewe kujaribu kuitumia wakati ilikuwa akizungumzia null,
wewe si kwenda kwa uwezo kupata taarifa hiyo.
Na hivyo kama vile, tulitaka kufanya kuhakikisha kwamba wakati wowote wewe ni mallocing,
wewe ni daima kuangalia kuona kama kwamba kumbukumbu aliyopewa na wewe ni null.
Na kama ni hivyo, basi tunaweza kusonga tarehe na mapumziko ya kificho yetu.
>> Hivyo sisi ni kwenda kwa initialize nodi mpya.
Sisi ni kwenda kufanya n mpya ni sawa na n.
Na kisha tunakwenda kufanya kuweka mpya pointer juu ya mpya
kwa null sababu sasa hivi hatuna wanataka chochote kwa kuwa na uhakika na.
Sisi hatuna wazo ambapo ni kwenda kuweka wewe,
na kisha kama tunataka kuingiza kichwani
basi tunaweza reassign pointer kichwa.
Je, kila mtu kufuata mantiki wapi yale yanayotokea?
>> Wote sisi ni kufanya ni kujenga mpya node, kuweka pointer null,
na kisha reassigning kwa kichwa kama sisi
kujua tunataka kuingiza katika kichwa.
Na kisha kichwa ni kwenda kuelekezea kwamba nodi mpya.
Kila mtu sawa kwa hilo?
>> Hivyo ni mchakato wa hatua mbili.
Nimepata hawawajui kwanza chochote wewe ni kujenga.
Kuweka kwamba pointer rejea, na kisha
Unaweza aina ya dereference pointer kwanza
na kumweka kuelekea nodi mpya.
Popote unataka kuingiza, mantiki kwamba ni kwenda kushikilia kweli.
>> Ni aina ya kama kumshirikisha vigezo muda.
Kumbuka, nimepata kuhakikisha kuwa wewe
si kupoteza wimbo wa kama wewe ni swapping.
Wewe unataka kuhakikisha kwamba una muda kutofautiana aina hiyo ya kuvaa
wimbo wa ambapo kwamba kitu ni kuhifadhiwa ili uweze
si kupoteza thamani yoyote katika kozi ya kama messing karibu na hiyo.
>> OK, hivyo kificho itakuwa hapa.
Nyie tuangalie baada ya kifungu.
Itakuwa pale.
>> Kwa hiyo mimi nadhani ni jinsi gani hii tofauti kama sisi alitaka
kuingiza ndani ya katikati au mwisho?
Je, mtu yeyote kuwa na wazo la nini pseudocode kama rejea mantiki
kwamba tunataka kuchukua kama tulitaka kwa kuingiza katika katikati?
Hivyo kama sisi alitaka kuingiza katika kichwa, kila sisi kufanya ni kujenga nodi mpya.
Sisi kuweka pointer ya kwamba nodi mpya kwa chochote kichwa,
na kisha sisi kuweka kichwa nodi mpya, sawa?
Kama tulitaka kuingiza katika katikati ya orodha, gani sisi kufanya?
>> Watazamaji: Ni ingekuwa bado kuwa mchakato sawa
ya kama kumshirikisha pointer na kisha kumshirikisha kwamba pointer,
lakini tunataka kuwa kuwapata humo.
>> ANDI PENG: Hasa, hivyo hasa mchakato huo isipokuwa wewe
na kuwapata wapi hasa wewe wanataka kuwa pointer mpya na kwenda katika,
hivyo kama nataka kuingiza ndani katikati ya wanaohusishwa list-- sawa,
hebu kusema kwamba ni orodha yetu wanaohusishwa.
Kama tunataka kuingiza haki hapa, tunakwenda kujenga nodi mpya.
Tunakwenda malloc.
Tunakwenda kujenga nodi mpya.
Tunakwenda kuwapa pointer hii nodi hapa.
>> Lakini tatizo kwamba hutofautiana kutoka ambapo kichwa ni
ni kwamba sisi alijua hasa ambapo kichwa ni.
Ilikuwa ni haki kwa mara ya kwanza, sawa?
Lakini hapa sisi tumepewa kuweka wimbo ya ambapo sisi ni kuingiza katika.
Kama sisi ni kuingiza yetu nodi hapa, sisi tumepewa
kuhakikisha kwamba mmoja uliopita kwa nodi hii
ni moja kwamba reassigns pointer.
Hivyo basi una aina ya kuweka wimbo wa mambo mawili.
Kama kuweka wimbo wa wapi huu nodi sasa ni kuingiza katika.
Unaweza pia kuwa na kuweka wimbo wa wapi nodi uliopita kwamba wewe ni kuangalia katika
Ilikuwa pale pia.
Kila mtu mzuri na kwamba?
SAWA.
>> Vipi kuhusu kuingiza ndani ya mwisho?
Kama nilitaka kuongeza kuwa here-- kama nilitaka kuongeza nodi mpya hadi mwisho wa orodha,
jinsi gani mimi kwenda juu ya kufanya hivyo?
Watazamaji: Hivyo kwa sasa, mwisho wa mtu alisema kwa null.
ANDI PENG: Naam.
Hasa, hivyo hii moja sasa zimeelekezwa kujua,
na hivyo mimi nadhani, kwa maana hii, ni rahisi sana kuongeza hadi mwisho wa orodha.
Wote una kufanya ni kuliweka sawa kwa null na kisha boom.
Haki pale, ni rahisi sana.
Rahisi sana.
>> Sawa na kichwa, lakini mantiki wewe
unataka kuhakikisha kwamba hatua wewe kuchukua kuelekea kufanya yoyote ya hii,
wewe ni kufuatia pamoja.
Ni rahisi sana kwa, katikati wa kanuni yako, unakamatwa juu,
loo, mimi nimepata kuyatumia wengi.
Sijui ambapo chochote ni akizungumzia.
Mimi wala hata kujua ambayo nodi mimi nina juu ya.
Nini kinaendelea?
>> Kupumzika, utulivu chini, kuchukua pumzi kina.
Kuteka nje orodha yako wanaohusishwa.
Kama umesema, Mimi najua wapi hasa Mimi haja ya kuingiza hii katika
na mimi kujua hasa jinsi ya reassign yangu kuyatumia, kiasi, rahisi picha
out-- kiasi, rahisi si kupata waliopotea katika mende wa kanuni yako.
Kila mtu sawa kwa hilo?
SAWA.
>> Kwa hiyo mimi nadhani dhana kwamba tuna si kweli kuongelea kabla ya sasa,
na mimi nadhani pengine si kukutana yet-- sana
ni aina ya concept-- ya juu ni kwamba sisi kweli kuwa data
muundo inayoitwa orodha doubly wanaohusishwa.
Hivyo kama wewe guys unaweza kuona, wote sisi ni kufanya ni kujenga
thamani halisi, ziada pointer juu ya kila mmoja wetu nodes
kwamba pia anazungumzia nodi uliopita.
Hivyo si tu kufanya tuna yetu nodes uhakika na moja ijayo.
Wao pia uhakika na mmoja uliopita.
Mimi nina kwenda kupuuza hizi mbili hivi sasa.
>> Hivyo basi una mlolongo kwamba unaweza hoja njia zote mbili,
na kisha ni kidogo rahisi kwa mantiki kufuata pamoja.
Kama hapa, badala ya kuweka wimbo wa, loo, mimi
kujua kwamba nodi hii ni moja kwamba nina reassign,
Naweza tu kwenda hapa na tu kuvuta uliopita.
Kisha mimi kujua hasa ambapo yaani, na kisha
Si lazima traverse ukamilifu wa orodha wanaohusishwa.
Ni kidogo rahisi zaidi.
>> Lakini kama vile, una mara mbili kiasi cha kuyatumia,
hiyo ni mara mbili kiasi cha kumbukumbu.
Ni mengi ya kuyatumia kwa kuweka wimbo wa.
Ni kidogo ngumu zaidi, lakini ni kidogo user kirafiki kutegemea zaidi
juu ya nini wewe kujaribu kukamilisha.
>> Hivyo aina hii ya data muundo kabisa ipo,
na muundo kwa ni sana, sana rahisi ila zote wewe ni kuwa ni,
badala ya pointer ijayo, wewe pia kuwa pointer uliopita.
Hiyo ni tofauti wote alikuwa.
Kila mtu mzuri na kwamba?
Baridi.
>> Haki wote, hivyo sasa mimi nina kwa kweli kutumia pengine
kama dakika 15 hadi 20 au wingi ya mapumziko ya muda katika sehemu
kuzungumza juu ya meza hash.
Ni wangapi wenu guys wamesoma pset5 spec?
Haki wote, nzuri.
Hiyo ni juu ya 50% ya kawaida.
Ni sawa.
>> Hivyo kama wewe guys utaona, uko changamoto katika pset5
itakuwa kutekeleza kamusi ambapo mzigo juu ya maneno 140,000
kwamba sisi kukupa na kuangalia Spell dhidi maandishi yote.
Tutaweza kukupa random vipande vya fasihi.
Tutaweza kukupa Odyssey.
Tutaweza kukupa Iliad.
Tutaweza kukupa Austin Powers.
>> Na changamoto yako itakuwa Spell kuangalia
kila neno moja katika yote ya Mkwawa wale
kimsingi kwa Spell kusahihisha yetu.
Na hivyo kuna sehemu chache ya kujenga pset hii,
kwanza unataka kuwa uwezo wa kweli mzigo
maneno yote katika yako kamusi, na kisha
wanataka kuwa na uwezo wa Spell kuangalia wote.
Na hivyo kama vile, wewe ni kwenda zinahitaji muundo data kwamba unaweza kufanya hivyo haraka
na kwa ufanisi na dynamically.
>> Hivyo nadhani rahisi njia ya kufanya hivyo,
pengine kuunda safu, sawa?
Njia rahisi ya kuhifadhi ni wewe Unaweza kuunda safu ya maneno 140,000
na tu kuwaweka wote huko na kisha traverse yao kwa kutafuta binary
au kwa uchaguzi au not-- pole hiyo kuchagua.
Unaweza aina yao na kisha traverse yao na tafuta binary au la tu linear
na maneno tu ya mwisho, lakini kwamba inachukua kiasi kikubwa cha kumbukumbu,
na siyo ufanisi sana.
>> Na hivyo sisi ni kwenda kuanza kuzungumza juu ya njia ya kufanya
mbio wakati wetu ufanisi zaidi.
Na lengo letu ni kupata wakati mara kwa mara ambapo
ni karibu kama arrays, ambapo unaweza kupata instantaneous.
Kama nilitaka kutafuta chochote, Nataka kuwa na uwezo wa haki,
boom, sioni ni hasa, na kuvuta ni nje.
Na hivyo muundo ambao tutaweza kuwa kuwa karibu sana
kuwa na uwezo wa kupata mara kwa mara muda, grail takatifu huu
katika programu ya mara kwa mara muda inaitwa meza hash.
Na hivyo Daudi zilizotajwa hapo awali [Inaudible] kidogo katika hotuba,
lakini tunakwenda kweli kupiga mbizi katika kina wiki hii
juu ya kipande hiyo kuhusu jinsi meza hash kazi.
>> Hivyo njia kwamba hash kazi meza, kwa mfano,
kama nilitaka kuhifadhi rundo la maneno, a rundo la maneno katika lugha ya Kiingereza,
Mimi inaweza kinadharia kuweka ndizi, apple, kiwi, maembe, jozi,
na tikiti maji yote juu tu safu.
Wangeweza wote fit katika na kuwa kupata.
Ni d kuwa aina ya maumivu ya kutafuta njia na upatikanaji,
lakini njia rahisi ya kufanya hivyo ni tuweze kujenga kweli muundo
aitwaye hash meza ambapo sisi hash.
Sisi kuendesha wote wa funguo wetu kwa njia ya heshi, equation,
kwamba anarudi yao yote katika aina fulani ya thamani
kwamba basi tunaweza kuhifadhi kwenye kimsingi safu ya orodha wanaohusishwa.
>> Na hivyo hapa, kama sisi alitaka kuhifadhi maneno ya Kiingereza,
tunaweza uwezekano tu, sijui Unajua, kugeuka barua zote kwanza
ndani ya baadhi ya aina ya idadi.
Na hivyo, kwa mfano, kama nilitaka Kuwa sawa na apple--
au kwa ripoti ya 0, na B kuwa sawa na 1,
tunaweza kuwa na viingilio 26 kwamba wanaweza kuhifadhi tu
wote wa barua ya alfabeti kwamba tutaweza kuanza na.
Na kisha tunaweza kuwa apple katika orodha ya 0.
Tunaweza kuwa na ndizi katika orodha ya 1, tikiti maji katika orodha ya 2,
na kadhalika na kadhalika.
Na hivyo kama nilitaka kutafuta meza yangu hash na upatikanaji apple,
Najua apple huanza na A, na mimi kujua hasa
kwamba ni lazima na hash meza katika ripoti 0 kwa sababu
ya kazi ya awali kupewa.
>> Hivyo mimi sijui, sisi ni user mpango ambapo
wewe utakuwa kushtakiwa kwa arbitrarily-- si kiholela,
na kujaribu kufikiri kufikiria equations nzuri
kuwa na uwezo wa kuenea nje wote wa maadili yako
kwa njia wanaweza kupata urahisi baadaye juu na kama equation
kwamba, wewe mwenyewe, kujua.
Hivyo kwa mantiki kama nilitaka kwenda maembe, najua, loo, ni kuanza kwa m.
Ni lazima ripoti ya 12.
Sina kutafuta njia chochote.
Najua exactly-- mimi naweza tu kwenda ripoti ya 12 na kuvuta kuwa nje.
>> Kila mtu wazi juu ya jinsi kazi hash meza ya kazi?
Ni aina ya tu safu ngumu zaidi.
Hayo ni yote ni.
SAWA.
>> Kwa hiyo mimi nadhani sisi kukimbia katika suala hili la kile
kinachotokea kama una mambo mbalimbali kwamba kukupa ripoti hiyo?
Hivyo kusema kazi yetu, yote ni alifanya alikuwa kuchukua barua kwamba kwanza
na kugeuka kuwa katika husika 0 kwa njia ya 25 index.
Hiyo ni sawa kabisa kama wewe tu moja ya kila mmoja.
Lakini pili kuanza kuwa zaidi, wewe ni
kwenda na kile kinachoitwa mgongano.
>> Hivyo kama mimi kujaribu kuingiza kuzika katika hash meza ambayo tayari ina ndizi juu ya jambo hilo,
nini kitatokea wakati wewe kujaribu kuingiza kwamba?
Mambo mabaya kwa sababu ndizi tayari ipo ndani ya ripoti
kwamba unataka kuhifadhi katika.
Berry aina ya ni kama ah, nini mimi?
Sijui wapi pa kwenda.
Je, mimi kutatua hili?
>> Na hivyo nyie mapenzi aina ya ona sisi kufanya jambo hili gumu
ambapo tunaweza aina ya kweli kujenga uhusiano orodha katika arrays wetu.
Na hivyo njia rahisi kufikiri kuhusu hili,
zote meza hash ni safu ya orodha wanaohusishwa.
Na hivyo, kwa maana kwamba, una safu hii nzuri ya kuyatumia,
na kisha kila pointer katika thamani kwamba, kwa kuwa ripoti,
unaweza kweli uhakika na mambo mengine.
Na hivyo kuwa haya yote tofauti minyororo kuja mbali ya moja kubwa safu.
>> Na hivyo hapa, kama mimi alitaka kuingiza berry,
Mimi najua, sawa, mimi nina kwenda kwa pembejeo hivyo kwa njia ya hash yangu kazi.
Mimi nina kwenda kuishia na ripoti ya 1, na kisha mimi nina kwenda kuwa na uwezo wa kuwa na
tu subset ndogo ya hii kubwa 140,000-neno kamusi.
Na kisha siwezi tu kuangalia kupitia 26/1 ya kwamba.
>> Na hivyo basi naweza tu kuingiza berry ama kabla au baada ndizi
kwa kesi hii?
Baada, sawa?
Na hivyo wewe ni kwenda kutaka kuingiza nodi hii baada ya ndizi,
na hivyo wewe ni kwenda kuingiza katika mkia wa orodha hiyo wanaohusishwa.
Mimi nina kwenda nyuma kwa slide huu uliopita,
hivyo guys unaweza kuona jinsi kazi hash kazi.
>> Hivyo kazi hash ni swala hilo kwamba wewe ni mbio namna mchango wako
kupitia kwa kupata chochote ripoti unataka hawawajui kuelekea.
Na hivyo, katika mfano huu, kila tulitaka kufanya ni kuchukua herufi ya kwanza,
kugeuka kuwa katika ripoti, basi sisi wanaweza kuhifadhi kwamba katika kazi yetu hash.
Wote sisi ni kufanya hapa ni tuko kuwabadili barua ya kwanza.
Hivyo keykey [0] ni herufi ya kwanza ya chochote kamba sisi ni kuwa,
sisi ni kupita katika.
Sisi ni kuwabadili kwamba kwa juu, na sisi ni subtracting na uppercase A,
hivyo kila kitu ni kufanya anatupa idadi
ambayo tunaweza hash maadili yetu kwenye.
>> Na kisha tunakwenda kurudi hash modulus SIZE.
Kuwa mwangalifu sana kwa sababu, kinadharia, hapa
hash thamani yako inaweza kuwa kubwa.
Ni inaweza tu kwenda juu na juu na juu.
Ni inaweza kuwa baadhi ya kweli, kweli thamani kubwa,
lakini kwa sababu hash meza yako kwamba umeunda tu ina 26 bahati,
wewe unataka kuhakikisha yako modulusing ili uweze
hawana run-- ni sawa Jambo kama queue-- yako
hivyo kwamba huna kukimbia mbali Chini ya hash yako kazi.
>> Unataka wrap ni kuzunguka nyuma njia ile ile katika [inaudible] wakati
alikuwa kama sana, barua kubwa sana, wewe
hakutaka kuwa kwa kukimbia tu mbali mwisho.
Same kitu hapa, wewe unataka kuhakikisha haina kukimbia mbali mwisho kwa wrapping
karibu na juu ya meza.
Hivyo hii ni tu sana rahisi heshi.
Yote alifanya alikuwa kuchukua kwanza barua ya chochote pembejeo yetu ilikuwa
na kugeuka kuwa katika ripoti kwamba tunaweza kuweka katika hash yetu meza.
>> Yeah, na hivyo kama nilivyosema hapo kabla, njia ambayo sisi kutatua migongano
katika hash yetu meza ni kuwa, kile tunachokiita, chaining.
Hivyo kama wewe kujaribu kuingiza nyingi maneno ambayo kuanza na kitu kimoja,
wewe ni kwenda na thamani moja hash.
Avocados na apple, kama wameweza kukimbia kwa njia ya kazi yetu hash,
ni kwenda kutoa wewe huo idadi, idadi ya 0.
Na hivyo njia sisi kutatua kwamba ni tuweze kweli aina ya kiungo wao
pamoja kupitia orodha wanaohusishwa.
>> Na hivyo kwa maana hii, nyie unaweza kuona aina
jinsi miundo takwimu ambazo tumekuwa kuweka awali
kama raisin wanaohusishwa orodha aina ya wanaweza kuja pamoja katika moja.
Na kisha unaweza kuunda mbali ufanisi zaidi miundo data
ambayo inaweza kushughulikia kiasi kubwa ya data, kwamba dynamically resize kutegemea
juu ya mahitaji yako.
Kila mtu wazi?
Kila mtu wa aina wazi juu ya nini kinatokea hapa?
>> Kama nilitaka insert-- nini matunda ambayo huanza na, mimi sijui,
B, zaidi ya berry, ndizi.
>> Watazamaji: Blackberry.
>> ANDI PENG: Blackberry, Blackberry.
Wapi Blackberry kwenda hapa?
Naam, sisi kweli si yamepangwa huu bado, lakini kinadharia
kama sisi alitaka kuwa hii katika mpango wa herufi,
ambapo lazima Blackberry kwenda?
>> Watazamaji: [inaudible]
>> ANDI PENG: Hasa, baada ya hapa, sawa?
Lakini kwa vile ni vigumu sana reorder-- mimi nadhani ni juu nyie.
Nyie Unaweza kabisa kutekeleza chochote unataka.
Njia bora zaidi ya kufanya hivyo labda
itakuwa kutatua yako wanaohusishwa orodha katika mpango wa herufi,
na hivyo wakati uko kuingiza mambo, unataka
kuwa na uhakika wa kuingiza yao ndani ya herufi
ili basi wakati uko kujaribu kutafuta yao,
huna traverse kila kitu.
Unajua hasa ambapo ni, na ni rahisi.
>> Lakini kama wewe aina ya kuwa mambo yamejaa nasibu,
bado uko kwenda na traverse ni anyways.
Na hivyo kama nilitaka tu kuingiza Blackberry hapa
na nilitaka kutafuta hivyo, najua, loo, Blackberry
lazima kuanza na orodha ya 1, hivyo mimi kujua mara mmoja tu kutafuta katika 1.
Na kisha naweza aina ya traverse orodha wanaohusishwa
mpaka mimi kupata Blackberry, na then-- yeah?
>> Watazamaji: Kama wewe ni kujaribu create-- Nadhani kama hii ni rahisi sana hash
kazi.
Na kama sisi alitaka kufanya tabaka mbalimbali ya kwamba kama,
OK, tunataka tofauti katika kama barua zote herufi
na kisha tena kwa mwingine kuweka kama wa barua herufi ndani ya kwamba,
ni sisi kuweka kama hash meza ndani ya meza hash,
au kama kazi ndani ya kazi?
Au ni that--
>> ANDI PENG: Kwa hiyo hash yako function-- hash meza yako
inaweza kuwa kama kubwa kama wewe unataka kwa.
Hivyo kwa mantiki hii, nilifikiri ilikuwa ni rahisi sana, sana
rahisi kwa mimi aina tu kwa kuzingatia juu ya barua ya neno la kwanza.
Na hivyo kuna chaguzi 26 tu.
Naweza tu kupata chaguzi 26 kutoka 0-25 kwa sababu wanaweza tu
kuanza kutoka A to Z. Lakini Kama alitaka kuongeza, pengine, zaidi utata
au kwa kasi kukimbia muda wa yako hash meza, wewe kabisa
anaweza kufanya kila aina ya mambo.
Unaweza kufanya yako mwenyewe equation kwamba anatoa
usambazaji zaidi katika yako maneno, kisha wakati wewe kutafuta,
ni kwenda kuwa kasi zaidi.
>> Ni kabisa hadi nyie jinsi gani unataka kutekeleza jambo hilo.
Fikiria kama ndoo tu.
Kama nilitaka kuwa 26 ndoo, mimi nina kwenda
aina mambo ndani ya ndoo hizo.
Lakini mimi nina kwenda na rundo ya mambo katika kila ndoo,
hivyo kama unataka kufanya hivyo kasi na ufanisi zaidi,
basi mimi na mia ndoo.
>> Lakini basi una kufikiri njia ya kutatua mambo ili kwamba wao ni
katika ndoo sahihi wanapaswa kuwa katika.
Lakini basi wakati wewe kweli wanataka kuangalia kwamba ndoo,
ni mengi kwa kasi kwa sababu kuna chini ya mambo katika kila ndoo.
Na hivyo, yeah, hiyo ni kweli hila kwa nyie katika pset5
ni kwamba wewe utakuwa na changamoto ya kujenga tu
chochote ni ufanisi zaidi kazi unaweza kufikiria kuwa
uwezo wa kuhifadhi na kuangalia maadili haya.
>> Kabisa juu nyie Hata hivyo unataka kufanya hivyo,
lakini hiyo ni hatua nzuri kwa kweli.
Kwamba aina ya mantiki wewe wanataka kuanza kufikiria juu ya
ni, vizuri, kwa nini sio mimi kufanya ndoo zaidi.
Na kisha mimi kuwa na kutafuta mambo kidogo, na kisha labda mimi
kuwa tofauti heshi.
>> Naam, kuna mengi ya njia za kufanya hivyo pset, baadhi ni kwa kasi zaidi kuliko wengine.
Mimi nina kabisa kwenda kuona ni jinsi gani siku ya kufunga ilikuwa kwa kasi nyie itakuwa
kuwa na uwezo wa kupata kazi yako ya kufanya kazi.
OK, kila mtu ni nzuri juu ya chaining na hash meza?
Ni kweli kama rahisi sana dhana kama wewe kufikiri juu yake.
Wote ni ni kutenganisha chochote pembejeo yako ni ndani ya ndoo,
kuchagua yao, na kisha kutafuta unaorodhesha kwamba kuna kuhusishwa na.
>> Baridi.
Haki zote, sasa tuna aina mbalimbali muundo wa data kwamba wito mti.
Hebu kwenda juu na majadiliano juu inajaribu ambayo ni tofauti,
lakini katika jamii hiyo.
Kimsingi, mti zote ni badala ya kuandaa data kwa njia linear
kwamba meza hash does-- wewe kujua, ni got juu na chini
na kisha aina ya kuunganisha mbali wa hili mti ina juu ambayo wewe piga mzizi,
na kisha ina majani pande zote.
>> Na hivyo wote una hapa ni tu nodi juu
kwamba pointi kwa nodes nyingine, kwamba pointi kwa nodes zaidi, na kadhalika na kadhalika.
Na hivyo wewe tu na matawi kugawanyika.
Ni tu njia nyingine ya kuendesha data, na kwa sababu sisi kuiita mti,
nyie just-- ni tu inatokana nje kuangalia kama mti.
Hiyo ni kwa nini sisi kuiita miti.
>> Meza hash inaonekana kama meza.
Mti tu inaonekana kama mti.
Wote ni tofauti ni njia ya kuandaa nodes
kutegemea na nini mahitaji yako ni.
>> Hivyo kuwa mzizi na basi una majani.
Njia hiyo tunaweza hasa kufikiri juu yake ni mti binary,
mti binary ni aina maalum ya mti
ambapo kila nodi tu pointi kwa, katika max, nodes wengine wawili.
Na hivyo hapa una tofauti ulinganifu katika mti yako
ambayo inafanya kuwa rahisi kwa aina ya kuangalia nini maadili ni kwa sababu basi
na daima kushoto au kulia.
Kuna kamwe kama tatu kushoto kutoka kushoto au wa nne kutoka kushoto.
Ni tu una kushoto na kulia na unaweza kutafuta ama wale wawili.
Na hivyo kwa nini hii ni muhimu?
Njia kwamba hii ni muhimu ni kama wewe ni kuangalia
kutafuta njia maadili, haki?
Badala ya kutekeleza mapacha tafuta katika makosa safu,
kama alitaka kuwa na uwezo wa kuingiza nodes na kuchukua nodes katika mapenzi na pia
kuhifadhi la uwezo wa kutafuta binary.
Hivyo kwa njia hii, sisi ni aina ya tricking-- kumbuka wakati sisi
Alisema orodha wanaohusishwa hawawezi tafuta binary?
Sisi ni aina ya kujenga mfumo wa data kwamba mbinu kwamba katika kufanya kazi.
>> Na orodha hiyo kwa sababu wanaohusishwa ni linear, wao tu zimeunganishwa moja baada ya nyingine.
Tunaweza aina ya kuwa aina mbalimbali ya kuyatumia
hatua hiyo kwa nodes mbalimbali ambayo inaweza kutusaidia kwa utafutaji.
Na hivyo hapa, kama nilitaka kuwa binary tafuta mti,
Mimi najua kuwa katikati yangu kama 55.
Mimi tu kwenda kujenga kwamba kama katikati wangu, kama mzizi yangu,
na kisha mimi nina kwenda na maadili spin off yake.
>> Hivyo hapa, kama mimi nina kwenda kutafuta thamani ya 66, siwezi kuanza saa 55.
Ni 66 kubwa zaidi kuliko 55?
Ndiyo ni, hivyo ninajua Mus kutafuta i n pointer haki ya mti huu.
Mimi kwenda 77.
OK, ni 66 chini ya au mkubwa kuliko 77?
Ni chini ya, hivyo unajua, loo, kwamba ina kuwa kushoto nodi.
>> Na hivyo hapa sisi ni aina ya kuhifadhi zote ya mambo makubwa kuhusu arrays,
hivyo kama nguvu resizing ya vitu, kuwa
uwezo wa kuingiza na kufuta katika mapenzi, bila kuwa na wasiwasi kuhusu fasta
kiasi cha nafasi.
Sisi bado kuhifadhi wote wa mambo hayo ya ajabu
wakati pia kuwa na uwezo wa kuhifadhi kuingia na kutafuta muda wa kutafuta binary
Hakika sisi tulikuwa tu hapo awali uwezo wa kupata maneno.
>> New data muundo, aina ya tata kutekeleza, nodi.
Kama unaweza kuona, yote ni ni struct nodi ya
ni kwamba una kushoto na pointer haki.
Hayo ni yote ni.
Hivyo badala ya kuwa x au uliopita.
Una kushoto au kulia, na kisha unaweza aina ya kiungo wao pamoja
Hata hivyo hivyo kuchagua.
>> OK, sisi ni kweli kwenda tu kuchukua dakika chache.
Hivyo sisi ni kwenda na kurudi hapa.
Kama nilivyosema hapo awali, Mimi aina ya kuelezwa
mantiki nyuma jinsi sisi ingekuwa kutafuta njia hii.
Sisi ni kwenda kujaribu pseudocoding nje hii kuona
kama tunaweza aina ya kuomba mantiki hiyo ya kutafuta binary
na aina mbalimbali ya muundo data.
Kama wewe guys wanataka kuchukua kama wanandoa Dakika tu kufikiri juu ya hili.
SAWA.
Haki wote, mimi nina kwenda kwa kweli kutoa tu wewe the-- hapana,
tutaweza majadiliano juu pseudocode kwanza.
Hivyo haina mtu yeyote wanataka kutoa kumchoma katika kile
Jambo la kwanza unataka kufanya wakati wewe ni mapya nje kutafuta ni?
Kama sisi ni kuangalia kwa thamani ya 66, nini
Jambo la kwanza tunataka kufanya kama tunataka binary tafuta mti huu?
>> Watazamaji: Unataka kuangalia haki na kuangalia kushoto na kuona [inaudible]
idadi kubwa.
>> ANDI PENG: Yeah, kwa uhakika.
Hivyo wewe ni kwenda kuangalia mzizi wako.
Kuna kura ya njia unaweza kupiga hivyo, watu wako mzazi nodi kusema.
Mimi kama kusema mzizi sababu hiyo ni kama mizizi ya mti.
Wewe ni kwenda kuangalia nodi mizizi yako, na wewe ni
kwenda kuona ni mkubwa 66 zaidi kuliko au chini ya 55.
Na kama ni kubwa kuliko, vizuri, ni kubwa kuliko, wapi tunataka kuangalia?
Ambapo tunataka kutafuta sasa, sawa?
Tunataka kutafuta nusu haki ya mti huu.
>> Hivyo tuna, kwa urahisi, pointer kwamba pointi na haki.
Na hivyo basi tunaweza kuweka mzizi wetu mpya kuwa 77.
Tunaweza tu kwenda popote pointer ni akizungumzia.
Naam, loo, hapa sisi ni mapya katika 77, na tunaweza tu
kufanya hivyo recursively tena na tena.
Kwa njia hii, wewe aina ya kuwa na kazi.
Una njia ya kutafuta kuwa wewe unaweza tu kurudia tena na tena na tena,
kulingana na pale unataka kuangalia mpaka hatimaye kupata thamani
kwamba wewe ni kutafuta.
Mantiki?
>> Mimi nina kuhusu kuonyesha halisi kanuni, na ni mengi ya kificho.
Hakuna haja ya kituko nje.
Tutaweza majadiliano kwa njia hiyo.
>> Kwa kweli, hakuna.
Hiyo ilikuwa tu pseudocode.
OK, kwamba mara tu pseudocode, ambayo ni kidogo ngumu,
lakini ni kabisa faini.
Kila mtu kufuatia pamoja hapa?
Kama mzizi ni null, kurudi uongo kwa sababu kwamba maana yake
wewe hawana hata kitu chochote pale.
>> Kama mzizi n ni thamani, hivyo kama hutokea kwa kuwa moja wewe ni kuangalia,
basi wewe ni kwenda na kurudi kweli kwa sababu unajua wewe kupatikana.
Lakini kama thamani ni chini kuliko mizizi ya n, uko
kwenda kutafuta kushoto mtoto au jani kushoto,
chochote unataka simu yake.
Na kama thamani ni mkubwa kuliko mizizi, wewe ni kwenda kutafuta mti wa kulia,
basi tu kukimbia kazi njia ya kutafuta tena.
>> Na kama mzizi ni null, kwamba kuwa ina maana umefanya kufikiwa mwisho?
Hiyo ina maana wewe huna zaidi majani zaidi ya kutafuta,
basi, unajua, loo, mimi nadhani ni si katika hapa
kwa sababu baada ya Nimekuwa inaonekana kupitia jambo zima na siyo hapa,
tu wanaweza kuwa hapa.
>> Je, hiyo mantiki kwa kila mtu?
Hivyo ni kama tafuta binary kuhifadhi uwezo wa orodha wanaohusishwa.
Baridi, na hivyo Aina ya pili ya data ya muundo nyie
unaweza kujaribu kutekeleza juu ya pset yako, wewe tu kuwa na kuchagua njia moja.
Lakini labda njia mbadala kwa meza hash ni kile tunachokiita trie.
>> Trie zote ni ni aina maalum ya mti huo
ina maadili ambayo kwenda maadili mengine.
Hivyo badala ya kuwa mapacha mti kwa maana kwamba moja tu
Jambo unaweza kumweka kwa mbili, unaweza kuwa jambo moja hatua kwa wengi, mambo mengi.
Wewe kimsingi kuwa na arrays ndani ya ambayo unaweza kuhifadhi
kuyatumia kwamba uhakika na arrays mengine.
>> Hivyo nodi ya jinsi sisi ingekuwa kufafanua trie
ni tunataka kuwa na Boolean, neno c, sawa?
Hivyo nodi ni Boolean kama kweli au uongo,
Awali ya yote katika kichwa cha kwamba safu, ni hii neno?
Pili, unataka kuwa na kuyatumia kwa chochote wengine wao ni.
Kidogo ngumu, kidogo abstract, lakini Nami kueleza kile kwamba njia zote.
>> Hivyo hapa, juu, kama wewe na safu alitangaza tayari,
nodi ambapo una Boolean thamani kuhifadhiwa mbele
kwamba anaelezea ni hii neno?
Je, huyu si neno?
Na kisha una wengine wa safu yako kwamba
kweli maduka yote uwezekano wa nini inaweza kuwa.
Hivyo, kwa mfano, kama juu una
Jambo la kwanza kwamba anasema kweli au uongo, ndiyo au hapana, hii ni neno.
>> Na kisha una 0 hadi 26 ya barua kwamba unaweza kuhifadhi.
Kama nilitaka kutafuta hapa kwa popo, mimi kwenda juu
na mimi kuangalia kwa B. Mimi sioni B katika wangu safu, na hivyo najua, sawa, ni B neno?
B ni si neno, hivyo hivyo Mimi lazima kuweka kutafuta.
Mimi kwenda kutoka B, na mimi kuangalia kwa pointer kwamba B pointi kuelekea
na naona safu mwingine wa habari, muundo huo kwamba tulikuwa na kabla.
>> Na here-- loo, ijayo barua katika [inaudible] ni A.
Hivyo sisi kuangalia katika safu hiyo.
Tunaona thamani ya nane, na kisha sisi kuangalia kuona, loo,
hey, ni kwamba neno, ni B-A neno?
Wala si kauli.
Sisi tumepewa kuendelea kutafuta.
>> Na hivyo basi sisi kuangalia kwa ambapo pointer ya pointi,
na inaelekeza katika njia nyingine katika ambayo tuna thamani zaidi kuhifadhiwa.
Na hatimaye, sisi kupata B-A-T, ambayo ni neno la Mungu.
Na hivyo wakati mwingine ukiangalia, wewe ni kwenda
kuwa na kwamba hundi ya, ndiyo, kazi hii Boolean ni kweli.
Na hivyo kwa maana tuko aina ya kuwa mti na arrays.
>> Hivyo basi unaweza aina ya kutafuta chini.
Badala ya hashing kazi na kumshirikisha maadili na orodha wanaohusishwa,
unaweza tu kutekeleza trie kwamba utafutaji downwords.
Kweli, kweli ngumu mambo ya ajabu.
Si rahisi kufikiria kuhusu sababu mimi nina kama kutema wengi miundo data nje
saa wewe, lakini anafanya kila mtu wa aina kuelewa jinsi mantiki ya hii kazi?
>> OK, baridi.
Hivyo B-A-T, na kisha wewe ni kwenda kutafuta.
Wakati ujao wewe ni kwenda kuona, loo, hey, ni kweli,
hivyo najua hii ni lazima neno.
>> Same kitu kwa zoo.
Hivyo hapa ni jambo sahihi sasa, kama sisi alitaka kutafuta zoo, sasa hivi,
sasa zoo siyo neno katika kamusi yetu
kwa sababu, kama wewe guys unaweza kuona, nafasi ya kwanza kwamba tuna Boolean
kurudi kweli ni mwishoni mwa zoom.
Tuna Z-O-O-M.
>> Na hivyo hapa, sisi si kweli kuwa neno, bustani ya wanyama, katika kamusi yetu
kwa sababu sanduku huu kuangalia si checked.
Hivyo kompyuta haina tunajua kwamba zoo ni neno
kwa sababu kwa njia hiyo tumekuwa kuhifadhiwa hivyo, tu kuvuta hapa
kweli ina thamani Boolean hiyo imekuwa akageuka kweli.
Hivyo kama tunataka Insert neno, bustani ya wanyama, katika kamusi yetu,
jinsi gani sisi kwenda juu ya kufanya hivyo?
Tufanye nini una kufanya ili kuhakikisha yetu kompyuta anajua kwamba Z-O-O ni neno
na si neno la kwanza ni Z-O-O-M?
>> Watazamaji: [inaudible]
>> ANDI PENG: Hasa, sisi unataka kuhakikisha kwamba hii
hapa, kwamba thamani Boolean ni kuchunguzwa mbali kwamba ni kweli.
Z-O-O, kisha tunakwenda kuangalia kwamba, hivyo sisi kujua hasa, hey, zoo ni neno.
Mimi nina kwenda kuwaambia kompyuta kwamba ni neno hivyo
kwamba wakati hundi ya kompyuta, anajua kwamba zoo ni neno.
>> Kwa sababu kumbuka data haya yote miundo, ni rahisi sana kwa ajili yetu
kusema, loo, popo neno.
Zoo neno.
Zoom neno.
Lakini wakati wewe ni kujenga yake, kompyuta hana wazo.
>> Hivyo kuwa na kuwaambia ni hasa katika hatua gani ni hii neno?
Katika hatua gani ni kuwa si neno?
Na katika hatua gani kufanya mimi haja ya kutafuta vitu,
na katika hatua gani gani mimi haja ya kwenda baada ya hapo?
Kila mtu wazi ya kwamba?
Baridi.
>> Na hivyo basi huja tatizo la jinsi gani sisi
kwenda juu kuingiza kitu hiyo ni kweli si huko?
Basi hebu tu kusema tunataka Insert neno, kuoga, ndani ya trie yetu.
Kama nyie unaweza kuona kama sasa wote tuna sasa ni B-A-T,
na hii muundo mpya data kulikuwa na painti kwamba
Alisema kwa sababu sisi kudhani null kwamba, loo, hakuna maneno baada ya B-A-T,
kwa nini tunahitaji kuweka kuwa na mambo baada ya hapo T.
>> Lakini tatizo lililojitokeza kama sisi kufanya wewe wanataka kuwa na neno kwamba inakuja baada ya
T.
Kama una kuoga, uko atataka H haki.
Na hivyo njia tunakwenda kufanya hivyo ni tunakwenda kujenga nodi tofauti.
Sisi siyo allot chochote kiasi ya kumbukumbu kwa ajili ya safu hii mpya,
na tunakwenda reassign kuyatumia.
>> Tunakwenda kuwapa H, Awali ya yote, null hii,
tunakwenda kujikwamua.
Tunakwenda kuwa na H hatua kwenda chini.
Kama tunaona H, tunataka kwenda mahali pengine.
>> Katika hapa, tunaweza kisha kuangalia mbali ndiyo.
Kama sisi kugonga H baada T, loo, basi tunajua kwamba huyu ndiye neno.
Boolean ni kwenda na kurudi kweli.
Kila mtu wazi juu ya jinsi yaliyotokea?
SAWA.
>> Hivyo kimsingi, wote wa miundo haya data
kwamba tumeenda juu leo, nimekuwa gone juu yao kweli, kweli haraka
na si kwa kiasi katika undani, na hiyo ni sawa.
Mara baada ya kuanza messing pamoja na hayo, wewe utakuwa na
kuweka wimbo wa wapi kuyatumia yote ni,
nini kinaendelea katika yako miundo data, nakadhalika.
Wao utakuwa muhimu sana, na ni juu yako
guys kwa kabisa kufikiri jinsi unataka kutekeleza mambo.
>> Na hivyo pset4, ya 5-- loo, kwamba ni makosa.
Pset5 ni misspellings.
Kama nilivyosema hapo kabla, wewe ni kwenda, mara moja tena, download chanzo kanuni na kutuacha.
Kuna kwenda kuwa kuu tatu mambo wewe utakuwa kupakua.
Itabidi kushusha Mkwawa, kers, na maandiko.
>> Mambo hayo yote ni watu ama Mkwawa wa maneno
kwamba tunataka kuangalia au mtihani wa habari
kwamba tunataka Spell hundi.
Na hivyo Mkwawa sisi kutoa unaenda
kukupa maneno halisi kwamba tunataka kuhifadhi kwa namna fulani katika njia hiyo ni
ufanisi zaidi kuliko safu.
Na kisha maandiko ni kwenda kuwa nini tuko
kuuliza wewe Spell kuangalia kuhakikisha maneno yote kuna maneno halisi.
>> Na hivyo vitalu tatu ya mipango ambayo tutaweza kukupa
zinaitwa dictionary.c, dictionary.h, na speller.c.
Na hivyo wote dictionary.c gani ni nini wewe aliuliza kutekeleza.
Ni mizigo maneno.
Ni uchawi hundi yao, na hufanya uhakika kwamba kila kitu ni kuingizwa vizuri.
>> diction.h ni faili maktaba kwamba anatangaza kazi hizo zote.
Na speller.c, tunakwenda kukupa.
Huna haja ya kurekebisha yoyote ya hiyo.
Speller.c zote haina ni kuchukua kwamba, mizigo yake, hundi kasi yake,
vipimo benchmark ya kama jinsi haraka uko na uwezo wa kufanya mambo.
>> Ni speller.
Tu wala fujo na hilo, lakini kufanya uhakika wewe kuelewa nini ni kufanya.
Sisi kutumia kazi kuitwa getrusage kwamba vipimo utendaji wa Spell yako
kusahihisha.
All yake ni kimsingi mtihani wakati wa kila kitu katika kamusi yako,
ili kuhakikisha kuelewa.
Kuwa makini na si fujo na hayo, au mambo kingine si kukimbia vizuri.
>> Na wingi wa changamoto hii ni kwa nyie kweli kurekebisha dictionary.c.
Tunakwenda kukupa Maneno 140,000 katika kamusi.
Tunakwenda kukupa Nakala faili kwamba ina maneno hayo,
na tunataka kuwa na uwezo wa kuandaa yao katika meza hash au trie
kwa sababu wakati tunakuomba uchawi check-- kufikiria kama wewe ni uchawi
kuangalia kama Odyssey Homer ya.
Ni kama kubwa, kubwa ya mtihani huu.
>> Hebu fikiria kama kila moja neno alikuwa na kuangalia
kupitia safu ya 140,000 maadili.
Ambayo ingeweza kuchukua milele kwa mashine yako kukimbia.
Hii ndiyo sababu tunataka kuandaa wetu data katika ufanisi zaidi miundo data
kama vile hash meza au trie.
Na kisha nyie Unaweza aina ya wakati wewe kutafuta upatikanaji
mambo urahisi zaidi na haraka zaidi.
>> Na hivyo kuwa makini kutatua migongano.
Wewe ni kwenda kupata rundo maneno ya kwamba kuanza na A.
Wewe ni kwenda kupata maneno rundo kwamba kuanza na B. Hadi wewe
guys jinsi gani unataka kulitatua.
Labda kuna zaidi ufanisi heshi
kuliko tu barua ya kwanza ya kitu, na hivyo hiyo ni juu yako
guys aina ya kufanya chochote unataka.
>> Labda unataka kuongeza barua zote kwa pamoja.
Labda unataka kama kufanya mambo weird akaunti kwa idadi ya herufi,
chochote.
Hadi nyie jinsi gani unataka kufanya.
Kama unataka kufanya meza hash, kama wewe wanataka kujaribu trie, kabisa juu yako.
Mimi kuonya kabla ya muda kwamba trie ni kawaida vigumu kidogo zaidi
kwa sababu tu kuna mengi kuyatumia zaidi ya kuweka wimbo wa.
Lakini kabisa juu nyie.
Ni mbali zaidi ufanisi katika matukio mengi.
Unataka kweli na uwezo wa kuweka wimbo wa wote wa kuyatumia yako.
Kama kufanya kitu kimoja kwamba mimi alikuwa akifanya hapa.
Wakati wewe ni kujaribu kuingiza maadili katika meza hash au kufuta,
kuhakikisha kwamba uko kweli kuweka wimbo
ya ambapo kila kitu ni kwa sababu ni kweli rahisi kwa kama mimi nina
kujaribu kuingiza kama neno, andy.
Hebu tu kusema kwamba neno halisi, neno, andy,
ndani ya orodha kubwa ya maneno.
>> Kama mimi tu kutokea kwa reassign pointer vibaya, oops,
huenda kuna ukamilifu wa mapumziko ya orodha yangu wanaohusishwa.
Sasa neno tu mimi kuwa ni andy, na sasa
maneno yote mengine katika kamusi zimepotea.
Na hivyo unataka kuhakikisha kuweka wimbo wa wote wa kuyatumia yako
au mwingine ni kwenda kupata matatizo makubwa katika kanuni yako.
Kuteka mambo ya nje kwa makini hatua kwa hatua.
Inafanya kuwa rahisi sana kufikiria.
>> Na Mwisho, unataka kuwa na uwezo wa mtihani utendaji wako wa mpango wako
juu ya bodi kubwa.
Kama nyie kuchukua kuangalia CS50 hivi sasa,
tuna kile kinachoitwa bodi kubwa.
Ni alama karatasi ya kasi Spell mara kuangalia katika yote ya CS50
sasa hivi, nadhani juu kama 10 Mara Nadhani nane kati yao ni wafanyakazi.
Kweli tunataka nyie kutupiga.
>> Sisi sote walikuwa wakijaribu kutekeleza kificho kwa kasi iwezekanavyo.
Tunataka nyie kujaribu changamoto sisi na kutekeleza kwa kasi zaidi kuliko sisi sote
unaweza.
Na hivyo hii ni kweli mara ya kwanza kwamba sisi ni
kuuliza nyie kufanya pset kwamba unaweza kweli kufanya katika njia yoyote
Unataka.
>> Mimi daima kusema, hii ni sawa na zaidi ufumbuzi halisi ya maisha, sawa?
Nasema, hey, mimi haja ya wewe kufanya hivyo.
Kujenga mpango huo hana huu kwa ajili yangu.
Kufanya hivyo hata hivyo unataka.
Mimi tu kujua kwamba nataka kufunga.
Hiyo ni changamoto yako kwa wiki hii.
Nyie, tunakwenda kukupa kazi.
Tunakwenda kukupa changamoto.
Na kisha ni juu nyie kabisa tu kufikiri
nini haraka na wengi njia bora ya kutekeleza hili.
Yeah?
>> Watazamaji: Je, sisi kuruhusiwa ikiwa alitaka kufanya utafiti wa njia kasi
kufanya meza hash online, tunaweza kufanya kuwa na wanaelezea kificho mtu mwingine?
ANDI PENG: Yeah, kabisa faini.
Hivyo kama wewe guys kusoma spec, kuna mstari
katika spec kwamba anasema nyie ni bure kabisa kufanya utafiti wa hash
kazi juu ya nini ni baadhi ya kazi wepesi hash
kuendesha mambo kwa njia kama muda mrefu kama wewe wanaelezea kwamba kanuni.
Hivyo baadhi ya watu kuwa tayari figured nje ya njia haraka
za kufanya uchawi checkers, ya haraka njia za kuhifadhi taarifa.
Kabisa juu yako guys kama wewe wanataka tu kuchukua kwamba, haki?
Kuhakikisha wewe ni akitoa mfano.
Changamoto hapa kweli kwamba sisi ni kujaribu kwa mtihani
ni kuhakikisha kwamba unajua njia yako karibu kuyatumia.
Mbali kama wewe kutekeleza halisi heshi
na kuja na kama math kufanya hivyo,
nyie unaweza utafiti chochote mbinu online nyie unataka.
Yeah?
>> Watazamaji: Je, sisi kutaja tu kwa kutumia [inaudible]?
>> ANDI PENG: Naam.
Unaweza tu, katika maoni yako, unaweza wanaelezea kama, loo,
kuchukuliwa kutoka yada, yada, yada, heshi.
Mtu yeyote una maswali yoyote?
Sisi kwa kweli breezed kupitia sehemu leo.
Mimi nitakuwa hapa kwa kujibu maswali vilevile.
>> Pia, kama nilivyosema, ofisi masaa usiku wa leo na kesho.
Spec wiki hii ni kweli super rahisi na super short kusoma.
Napenda kupendekeza kuchukua kuangalia, tu kusoma kwa njia ya ukamilifu wake.
>> Na Zamyla kweli anatembea wewe kupitia kila moja ya kazi
wewe haja ya kutekeleza, na hivyo ni sana, wazi sana jinsi ya kufanya kila kitu.
Tu kuhakikisha uko kuweka wimbo wa kuyatumia.
Hii ni pset changamoto sana.
>> Siyo changamoto kwa sababu kama, loo, dhana ni hivyo zaidi
ngumu, au una kujifunza sana mpya syntax njia
kwamba alifanya kwa pset mwisho.
Pset hii ni ngumu kwa sababu kuna watu kuyatumia wengi,
na kisha ni sana, ni rahisi sana kwa mara nyingine una mdudu katika kanuni yako hawataweza
kupata ambapo kwamba mdudu ni.
>> Na hivyo kamili na imani mkubwa katika wewe guys kuwa na uwezo wa kuwapiga yetu [inaudible]
spellings.
Mimi kwa kweli si lolote yangu imeandikwa bado, lakini mimi nina tayari kuandika mgodi.
Hivyo wakati wewe ni kuandika wenu, mimi itakuwa kuandika mgodi.
Mimi nina kwenda kujaribu kufanya yangu kwa kasi kuliko yako.
Tutaona ambaye ana moja ya haraka sana.
>> Na ndiyo, mimi kuona yote ya nyie hapa Jumanne.
Mimi kukimbia aina kama warsha pset.
Wote wa sehemu hii wiki ni warsha pset,
hivyo nyie kuwa na kura ya fursa kuomba msaada, masaa ya ofisi kama siku zote,
na mimi kwa kweli kuangalia mbele kwa kusoma wote wa guys wako kificho.
Nina Quizzes hapa ikiwa guys wanataka kuja kupata hizo.
Hayo ni yote.