>> SPIKA 1: zote haki, hivyo sisi ni nyuma.
Karibu CS50.
Hii ni mwisho wa wiki saba.
Hivyo kukumbuka kuwa wakati wa mwisho, sisi ilianza kuangalia kidogo kisasa zaidi
data miundo.
Tangu hadi sasa, wote tulikuwa kweli ovyo yetu ilikuwa hii safu.
>> Lakini kabla ya sisi kuondokana na safu kama si yote ya kuvutia, ambayo kwa kweli ni
kweli ni, ni nini baadhi ya pluses ya data hii rahisi
muundo wa hivi sasa?
Nini ni nzuri?
Hadi sasa kama tumeona?
Je, unayo?
Chochote.
>> MWANAFUNZI: [inaudible].
>> SPIKA 1: Ni nini hiyo?
>> MWANAFUNZI: [inaudible].
>> SPIKA 1: zisizohamishika kawaida.
OK, hivyo kwa nini ni kawaida fasta nzuri ingawa?
>> MWANAFUNZI: [inaudible].
>> SPIKA 1: OK, hivyo ni ufanisi katika maana ya kwamba unaweza kutenga
fasta kiasi cha nafasi, ambayo hopefully hasa ni kama vile
nafasi kama unataka.
Hivyo kwamba inaweza kuwa ni pamoja na kabisa.
>> Nini upande mwingine juu ya safu?
Yeah?
>> MWANAFUNZI: [inaudible].
>> SPIKA 1: zote - sorry?
>> MWANAFUNZI: [inaudible].
>> SPIKA 1: masanduku wote katika kumbukumbu au karibu na kila mmoja.
Na kwamba ni manufaa - kwa nini?
Hiyo ni kweli kabisa.
Lakini jinsi gani tunaweza kutumia kwamba kweli?
>> MWANAFUNZI: [inaudible].
>> SPIKA 1: Hasa, tunaweza kuweka wimbo wa ambapo kila kitu ni tu kwa kujua
moja ya anwani, yaani anuani ya kwanza Byte ya kwamba chunk ya kumbukumbu.
Au katika kesi ya kamba, anwani ya kwanza
Char katika kamba hiyo.
Na kutoka huko, tunaweza kupata mwisho wa kamba.
Tunaweza kupata kipengele cha pili, ya tatu kipengele, na kadhalika.
>> Na hivyo njia ya kuelezea dhana kwamba kipengele ni kwamba arrays kutupatia
random kupata.
Tu kwa kutumia mabano mraba nukuu na simu, unaweza kuruka kwa
kipengele maalum katika safu katika muda wa mara kwa mara, kubwa O
mmoja, hivyo kusema.
>> Lakini kuna kuwa baadhi downsides.
Nini safu si kufanya sana kwa urahisi?
Nini ni si nzuri wakati?
>> MWANAFUNZI: [inaudible].
>> SPIKA 1: Ni nini hiyo?
>> MWANAFUNZI: [inaudible].
>> SPIKA 1: Kupanua katika kawaida.
Hivyo downsides wa safu ni just kinyume cha kile
upsides ni.
Hivyo moja ya downsides ni kwamba ni kawaida fasta.
Hivyo unaweza si kweli kukua yake.
Unaweza reallocate chunk kubwa ya kumbukumbu, na kisha kuondoka mambo ya zamani
katika safu mpya.
Na kisha bure safu ya zamani, kwa mfano, kwa kutumia malloc au sawa
kazi kuitwa realloc, ambayo reallocates kumbukumbu.
>> Realloc, kama kando, anajaribu kutoa kumbukumbu hiyo ni karibu na safu
kwamba wewe tayari.
Lakini inaweza hoja mambo karibu kabisa.
Lakini katika muda mfupi, hiyo ni ghali, haki?
Kwa sababu kama una chunk ya kumbukumbu ya kawaida hii, lakini kweli unataka moja
ya kawaida hii, na unataka kuhifadhi mambo ya awali, una
takribani linear wakati kuiga mchakato kwamba mahitaji ya kutokea kutoka
umri wa safu mpya.
Na ukweli ni kuuliza uendeshaji mfumo tena na tena na
tena kwa chunks kubwa ya kumbukumbu unaweza kuanza kwa gharama ya baadhi ya muda pia.
Hivyo ni baraka na laana katika kujificha, ukweli kwamba haya arrays
ni ya ukubwa wa kudumu.
Lakini kama sisi kuanzisha badala kitu kama hii, ambayo sisi kuitwa wanaohusishwa
orodha, sisi kupata upsides chache na downsides chache hapa pia.
>> Hivyo orodha wanaohusishwa ni tu data muundo alifanya juu ya structs C katika hii
kesi, ambapo struct, kukumbuka, ni tu chombo kwa moja au zaidi maalum
aina ya vigezo.
Katika kesi hiyo, je, aina ya data kuonekana kuwa ndani ya struct kwamba
Mara ya mwisho sisi kuitwa nodi?
Kila moja ya hizi ni mistatili nodi.
Na kila moja ya mistatili ndogo ndani yake ni aina ya data.
Ni aina gani gani sisi kusema walikuwa Jumatatu?
Yeah?
>> MWANAFUNZI: [inaudible].
>> SPIKA 1: kutofautiana na pointer, au hasa zaidi, int, kwa n,
na pointer chini.
Wote wa wale kutokea kwa kuwa 32 bits, saa angalau kwenye kompyuta kama hii CS50
Appliance, na hivyo ni inayotolewa kwa usawa katika kawaida.
>> Hivyo kile ni kutumia pointer ingawa kwa inaonekana?
Kwa nini kuongeza hii mshale sasa wakati arrays walikuwa hivyo nzuri na safi na rahisi?
Kile ni pointer kufanya kwa ajili ya sisi katika kila aina ya nodes haya?
>> MWANAFUNZI: [inaudible].
>> SPIKA 1: Hasa.
Ni nawaambia ambapo moja ijayo.
Hivyo mimi aina ya kutumia mfano wa kutumia thread ya aina ya
thread nodes haya pamoja.
Na kwamba ni nini hasa sisi ni kufanya na kuyatumia kwa sababu kila moja ya haya
chunks ya kumbukumbu au anaweza kuwa na contiguous, nyuma kwa nyuma kwa nyuma
ndani ya RAM, kwa sababu kila wakati kuwaita malloc akisema, nipe kutosha
ka kwa nodi mpya, nguvu kuwa hapa au inaweza kuwa hapa.
Inaweza kuwa ni hapa.
Wewe tu sijui.
>> Lakini kwa kutumia kuyatumia katika anwani ya wale nodes, unaweza kuyashona
pamoja katika njia kwamba inaonekana kuibua kama orodha hata kama mambo haya ni ya
wote kuenea nje katika moja au mbili yako au yako gigabytes minne ya RAM
ndani ya kompyuta yako mwenyewe.
>> Hivyo upande wa chini, basi, ya orodha wanaohusishwa ni nini?
Nini bei tuko inaonekana kulipa?
>> MWANAFUNZI: [inaudible].
>> SPIKA 1: Zaidi nafasi, haki?
Tumekuwa, katika kesi hii, mara mbili ya kiasi wa nafasi kwa sababu tumeenda
kutoka 32 bits kwa kila node, kwa kila int, hivyo sasa bits 64 kwa sababu tuna
kuweka karibu pointer pia.
Kupata ufanisi zaidi kama struct yako ni kubwa kuliko jambo hili rahisi.
Kama wewe kweli kuwa mwanafunzi wa ndani ambayo ni ya wanandoa wa masharti kwa
jina na nyumba, labda idadi ID, labda baadhi ya maeneo mengine kabisa.
>> Hivyo kama una kubwa ya kutosha struct, basi labda gharama ya pointer ni
si kama mpango kubwa.
Hii ni kidogo ya kona katika kesi kwamba sisi ni kuhifadhi primitive vile rahisi
ndani ya orodha wanaohusishwa.
Lakini uhakika ni sawa.
Wewe ni dhahiri kutumia zaidi kumbukumbu, lakini wewe ni kupata
kubadilika.
Kwa sababu sasa kama nataka kuongeza kipengele katika mwanzo wa orodha hii,
Nina kutenga nodi mpya.
Na mimi tu update wale mishale na kwa namna fulani tu kusonga
baadhi ya kuyatumia kote.
>> Kama nataka kuingiza kitu katika katikati ya orodha, mimi hawana
kushinikiza kila mtu kando kama tulivyofanya katika kipindi cha wiki na kujitolea wetu ambao
kuwakilishwa safu.
Naweza tu kutenga nodi mpya na basi tu kumweka mishale katika
tofauti maelekezo kwa sababu haina kubaki katika halisi
kumbukumbu mstari wa kweli kama nimekuwa inayotolewa hapa kwenye screen.
>> Na kisha mwisho, kama unataka kuingiza kitu mwisho wa orodha, ni
hata rahisi.
Hii ni aina ya nukuu holela, lakini pointer 34 wa, kuchukua nadhani.
Nini thamani ya pointer wake wengi uwezekano inayotolewa aina ya kama miaka
shule antenna huko?
>> MWANAFUNZI: [inaudible].
>> SPIKA 1: Ni pengine null.
Na kwa kweli kwamba ni moja ya mwandishi uwakilishi wa null.
Na ni kwa sababu wewe kabisa null haja ya kujua ambapo mwisho wa wanaohusishwa
orodha ni, usije kushika zifuatazo na kufuatia na kufuatia mishale hizi
kwa baadhi ya thamani ya takataka.
Hivyo itakuwa null yanamaanisha kwamba hakuna zaidi nodes na haki ya idadi ya 34,
katika kesi hii.
>> Hivyo sisi kupendekeza kwamba tunaweza kutekeleza hii nodi katika kanuni.
Na tumeona aina hii ya syntax kabla.
Typedef tu amefafanua aina mpya kwa ajili ya nasi, inatupa kisawe kama
kamba ilikuwa kwa ajili ya * Char.
Katika kesi hiyo, ni kwenda kutupa shorthand nukuu ili struct nodi
unaweza badala tu kuandikwa kama nodi, ambayo ni safi sana.
Ni mengi chini verbose.
>> Ndani ya nodi ni inaonekana int kuitwa n, na kisha nodi struct *
ambayo ina maana hasa nini sisi alitaka mishale ya maana, pointer mwingine
nodi ya aina exact data.
Na napendekeza kwamba tunaweza kutekeleza tafuta kazi kama hii, ambayo kwa
mtazamo wa kwanza inaweza kuonekana tata kidogo.
Lakini hebu angalia katika mantiki yake.
>> Nivuke kwa appliance hapa.
Napenda kufungua faili inayoitwa orodha ya sifuri nukta h.
Na kwamba tu ina maana sisi tu kuona wakati iliyopita kwa ajili ya data hii
aina kuitwa nodi.
Hivyo tumekuwa kuweka kwamba katika faili dot h.
>> Na kama kando, hata ingawa hii mpango kwamba wewe ni juu ya kuona ni
si tata kwamba wote, ni kweli mkataba wakati wa kuandika mpango wa
kuweka mambo kama aina ya data, kuvuta constants wakati mwingine, ndani ya yako
header faili na si lazima katika yako C faili, hakika wakati wako
mipango ya kupata kubwa na kubwa, hivyo kwamba unajua ambapo wote kuangalia kwa
nyaraka katika baadhi ya kesi, au kwa misingi kama hii,
ufafanuzi wa aina fulani.
>> Kama mimi sasa kufungua orodha ya sifuri nukta c, taarifa mambo machache.
Ni pamoja na header files wachache, wengi ambayo tumekuwa kuona mbele.
Ni pamoja na kichwa yake mwenyewe faili.
>> Na kama kando, kwa nini hiyo ni mara mbili quotes hapa, kinyume na angle
mabano kwenye mstari kwamba Nimekuwa yalionyesha huko?
>> MWANAFUNZI: [inaudible].
>> SPIKA 1: Yeah hivyo ni faili za mitaa.
Hivyo kama ni faili za mitaa yako mwenyewe hapa kwenye mstari wa 15, kwa mfano, unaweza kutumia
quotes mbili badala ya mabano angled.
>> Sasa hii ni aina ya kuvutia.
Taarifa kwamba nimepata alitangaza kimataifa kutofautiana katika mpango huu juu ya mstari wa 18
iitwayo ya kwanza, wazo kuwa hii ni kwenda kuwa pointer kwanza
nodi katika orodha yangu wanaohusishwa, na nimekuwa initialized ni null, kwa sababu nimekuwa
si zilizotengwa yoyote halisi nodes bado tu.
>> Hivyo hii inawakilisha, pictorially, nini sisi aliona wakati iliyopita katika picha kama
kwamba pointer juu mbali mkono wa kushoto upande.
Hivyo sasa hivi, kwamba pointer hana mshale.
Badala yake ni null.
Lakini inawakilisha nini itakuwa anuani ya halisi ya kwanza
nodi katika orodha hii.
Hivyo nimekuwa kutekelezwa ni wa kimataifa kwa sababu, kama utaona, yote hii
haina mpango katika maisha ni kutekeleza orodha wanaohusishwa kwa ajili yangu.
>> Sasa mimi nimepata prototypes chache hapa.
Mimi aliamua kutekeleza makala kama kufutwa, kuingizwa, kutafuta, na
traversal -
mwisho kuwa tu kutembea katika orodha, uchapishaji nje mambo yake.
Na sasa hapa ni kawaida yangu kuu.
Na sisi si kutumia muda sana juu ya hizi tangu hii ni aina ya, hopefully
zamani kofia kwa sasa.
>> Mimi nina kwenda kufanya yafuatayo, wakati mtumiaji inashirikiana.
Hivyo moja, mimi nina kwenda magazeti nje orodha hii.
Na nimekuwa formatted kama cleanly kama mimi naweza.
Kama mtumiaji aina katika moja, ina maana kwamba wanataka kufuta kitu.
Kama mtumiaji aina mbili, kwamba maana ya wanataka kuingiza kitu.
Na kadhalika.
Mimi nina kwenda kisha kuchochea kisha kwa ajili ya amri.
Na kisha mimi naenda kutumia GetInt.
>> Hivyo hii ni kweli rahisi menuing interface ambapo wewe tu kuwa na aina
ramani ya simu kwa moja ya wale amri.
Na sasa nina nzuri safi kubadili Kauli hiyo ni kwenda kubadili juu
chochote mtumiaji typed in
Na kama wao typed moja, mimi itabidi kuwaita kufuta na kuvunja.
Kama wao typed mbili, mimi itabidi kuwaita kuingiza na kuvunja.
>> Na sasa taarifa nimekuwa kuweka kila ya haya juu ya mstari huo.
Hii ni uamuzi Stylistic.
Kawaida tumeona kitu kama hii.
Lakini mimi tu aliamua, kusema ukweli, mpango wangu inaonekana zaidi someka kwa sababu
ilikuwa ni nne tu kesi tu orodha ni kama hii.
Kabisa halali matumizi ya mtindo.
Na mimi naenda kufanya hii ya muda mrefu kama mtumiaji hana typed sifuri, ambayo mimi
aliamua itakuwa na maana wanataka kujiondoa.
>> Hivyo sasa taarifa ya nini mimi nina kwenda kufanya hapa.
Mimi nina kwenda huru orodha inaonekana.
Lakini zaidi juu ya kwamba katika muda tu.
Hebu kwanza kuendesha mpango huu.
Hivyo basi mimi kufanya terminal kubwa dirisha, dot kufyeka orodha 0.
Mimi nina kwenda mbele na kuingiza na kuandika mbili, idadi kama 50, na sasa
utaona orodha sasa ni 50.
Na maandishi yangu tu scrolled juu kidogo.
Hivyo sasa taarifa orodha ina simu 50.
>> Hebu kufanya mwingine Insert kwa kuchukua mbili.
Hebu aina katika idadi kama mmoja.
Orodha ya sasa ni moja, ikifuatiwa na 50.
Hivyo hii ni tu uwakilishi textual ya orodha.
Na hebu kuingiza moja zaidi ya simu kama namba 42, ambayo ni hopefully
kwenda kuishia katikati, kwa sababu programu hii katika aina fulani ni
mambo kama kuwekeza yao.
Hivyo kuna sisi kuwa nayo.
Super rahisi mpango kwamba angeweza kabisa wametumia safu, lakini mimi
kutokea kwa kutumia orodha wanaohusishwa hivyo tu naweza dynamically
kukua na kuogopa hilo.
>> Hivyo hebu tuangalie kwa ajili ya utafutaji, kama mimi kukimbia amri tatu, nataka kutafuta
kwa kusema, simu 43.
Na hakuna kitu ilikuwa inaonekana kupatikana, kwa sababu mimi got nyuma hakuna majibu.
Basi hebu kufanya hii tena.
Kutafuta.
Hebu tafuta kwa ajili ya 50, au tuseme kutafuta kwa ajili ya 42, ambayo ina nice
kidogo hila maana.
Na nimeona maana ya maisha huko.
Namba 42, kama hamjui kumbukumbu, Google yake.
Wote haki.
Hivyo kile ina mpango huu kufanyika kwa ajili yangu?
Ni tu kuruhusiwa mimi kuingiza hivyo mbali na kutafuta kwa ajili ya mambo.
>> Hebu haraka mbele, basi, kwa kwamba kazi ya sisi akapiga saa
Jumatatu kama kichocheo.
Hivyo kazi hii, mimi kudai, utafutaji kwa ajili ya kipengele katika orodha ya kwanza na
moja, na kusababisha mtumiaji na basi wito GetInt kupata int halisi
kwamba unataka kutafuta.
>> Basi taarifa hii.
Mimi nina kwenda kujenga variable muda katika mstari 188 kuitwa pointer -
PTR -
ingeweza kuitwa ni kitu chochote.
Na ni pointer nodi kwa sababu nalisema nodi * huko.
Na mimi nina initializing kuwa ni sawa na kwanza ili mimi na ufanisi wangu
kidole, hivyo kusema, juu sana kwanza kipengele cha orodha.
Hivyo kama mkono wangu wa kulia hapa ni PTR mimi nina akionyesha kitu kimoja kwamba kwanza
ananyoosha katika.
>> Hivyo sasa nyuma katika kanuni, kile kinachotokea ijayo -
hii ni dhana ya kawaida wakati iterating juu ya muundo kama
wanaohusishwa orodha.
Mimi nina kwenda kufanya yafuatayo wakati pointer si sawa na null Hivyo wakati
kidole yangu si akionyesha null baadhi thamani, kama pointer mshale n sawa n.
Tutaweza taarifa ya kwanza kwamba n ni nini mtumiaji typed katika GetInts kwa kuwaita hapa.
>> Na pointer mshale n maana yake nini?
Vizuri kama sisi kwenda nyuma ya picha hapa, kama nina kidole akionyesha
kwamba nodi kwanza zenye tisa, mshale kimsingi ina maana kwamba kwenda
nodi na kunyakua thamani katika eneo n, katika kesi hii, shamba data kuitwa n.
>> Kama kando - na tuliona hii michache ya wiki iliyopita wakati mtu aliuliza -
syntax hii ni mpya, lakini haina kutupatia nguvu kwamba sisi
hakuwa tayari.
Nini ilikuwa hii maneno sawa na kutumia nukta nukuu na nyota wanandoa
ya wiki iliyopita wakati sisi peeled nyuma safu hii mapema kidogo?
>> MWANAFUNZI: [inaudible].
>> SPIKA 1: Hasa, ilikuwa ni nyota, na basi ni nyota dot n, na
mabano hapa, ambayo inaonekana, kusema ukweli, nadhani mengi
zaidi fumbo kusoma.
Lakini nyota pointer, kama siku zote, njia kwenda huko.
Na mara moja uko huko, kile data shamba unataka kupata?
Vizuri kutumia nukuu dot kupata structs shamba data, na mimi
hasa wanataka n.
>> Kusema ukweli, napenda wanasema hii ni vigumu kusoma.
Ni vigumu kukumbuka ambapo wala mabano kwenda,
nyota na wote ya kwamba.
Hivyo dunia iliyopitishwa baadhi ya kisintaksia sukari, hivyo kusema.
Njia tu sexy ya kusema, hii ni sawa, na
labda zaidi Intuitive.
Kama pointer ni kweli pointer, mshale nukuu njia kwenda huko na kupata
shamba katika kesi hii inaitwa n.
>> Hivyo kama mimi kupata hiyo, taarifa ya nini mimi kufanya.
Mimi tu magazeti nje, nimeona asilimia i, plugging katika thamani kwa int kwamba.
Mimi wito kulala kwa moja ya pili tu ya aina mambo ya pause kwenye screen
kutoa user pili wa kunyonya kile tu kilichotokea.
Na kisha mimi kuvunja.
Vinginevyo, nini mimi?
Mimi update pointer sawa pointer mshale ijayo.
>> Hivyo tu kuwa wazi, hii ina maana kwenda huko, kutumia yangu zamani shule nukuu.
Hivyo hii ina maana tu ya kwenda chochote wewe ni akionyesha, ambayo kwa sana
kesi ya kwanza ni mimi nina akionyesha struct na tisa katika hilo.
Hivyo nimekuwa amekwenda huko.
Na kisha nukuu dot maana yake, kupata thamani saa ijayo.
>> Lakini thamani, hata kama ni inayotolewa kama nyembamba, ni idadi tu.
Ni anuani nambari.
Hivyo hii line moja ya kanuni, kama imeandikwa kama hii, zaidi fumbo
njia, au kama hii, kidogo zaidi njia angavu, tu ina maana hoja mkono wangu
na nodi ya kwanza kwa moja ijayo, na kisha moja ijayo, na kisha
ijayo mmoja, na kadhalika.
>> Hivyo sisi si kukaa juu ya nyingine utekelezaji wa kuingiza na kufuta
na traversal, wawili wa kwanza wa ambayo ni haki ya kushiriki.
Na nadhani ni rahisi kabisa ya kupata waliopotea wakati wa kufanya hivyo kwa maneno.
Lakini nini tunaweza kufanya hapa ni kujaribu kuamua jinsi
bora kufanya hivyo kuibua.
Kwa sababu napenda kupendekeza kwamba kama sisi wanataka kuingiza mambo ya ndani ya hii
zilizopo orodha, ambayo ina mambo tano -
9, 17, 22, 26, na 33 -
kama mimi walikuwa kwenda kutekeleza hili katika kanuni, mimi haja ya kufikiria jinsi ya kwenda
juu ya kufanya hii.
>> Na napenda kupendekeza kuchukua hatua mtoto ambapo, katika kesi hii I mean, ni nini
matukio inawezekana kwamba sisi anaweza kukutana kwa ujumla?
Wakati utekelezaji Insert kwa wanaohusishwa orodha, hii hutokea tu kuwa
maalum mfano wa ukubwa tano.
Vizuri kama unataka kuingiza idadi, kama kusema namba moja, na
kudumisha yamepangwa ili, ambapo wazi haina namba moja wanahitaji
kwenda katika mfano huu maalum?
Kama mwanzoni.
>> Lakini nini kuvutia kuna ni kwamba kama unataka kuingiza moja katika hili
orodha, nini pointer maalum mahitaji ya kuwa updated inaonekana?
Kwanza.
Hivyo napenda kusema, hii ni kesi ya kwanza kwamba sisi kutaka kufikiria,
mazingira ya kuwashirikisha kuingiza katika mwanzo wa orodha.
>> Hebu konoa labda kama rahisi au hata rahisi kesi, kiasi kuzungumza.
Tuseme nataka kuingiza namba 35 ili Iliyopangwa.
Ni wazi ni mali ya zaidi ya hapo.
Hivyo kile pointer wazi ni kwenda kuwa updated katika hali hiyo?
Pointer 34 ya kuwa si null lakini anwani ya struct
zenye namba 35.
Hivyo kwamba ni kesi mbili.
Hivyo tayari, mimi nina aina ya quantizing kiasi gani kazi mimi kufanya hapa.
>> Na hatimaye, wazi katikati kesi ni kweli kweli, katikati, kama nataka
kuingiza kitu kama kusema 23, kwamba huenda kati ya 23 na 26, lakini
sasa mambo kupata zaidi kidogo kushiriki kwa sababu gani
kuyatumia haja ya kuwa iliyopita?
Hivyo ni wazi 22 inahitaji kubadilishwa kwa sababu hawezi uhakika na 26 tena.
Yeye mahitaji kwa uhakika na node mpya ambayo Mimi itabidi kutenga kwa kumwita
malloc au baadhi ya sawa.
>> Lakini basi mimi pia haja ya kuwa nodi mpya, 23 katika kesi hii, kuwa na pointer yake
akionyesha nani?
26.
Na kuna kwenda kuwa utaratibu wa shughuli hapa.
Kwa sababu kama mimi kufanya hivyo kwa ujinga, na mimi kwa mfano kuanza mwanzoni mwa
orodha, na lengo langu ni kuingiza 23.
Na mimi kuangalia, je, ni mali ya hapa karibu tisa?
No
Je, ni mali ya hapa, karibu na 17?
No
Je, ni mali hapa karibu na 22?
Ndiyo.
>> Sasa kama mimi nina wajinga hapa, na si kufikiri hili kwa njia ya, mimi ili
kutenga nodi wangu mpya kwa 23.
Nipate update pointer kutoka nodi kuitwa 22, akizungumzia
ni kwenye nodi mpya.
Na kisha nini nina update pointer nodi mpya ya kuwa?
>> MWANAFUNZI: [inaudible].
>> SPIKA 1: Hasa.
Akionyesha 26.
Lakini Dammit kama sikuwa tayari update Pointer 22 wa uhakika katika guy hii, na
sasa mimi na yatima, wengine ya orodha, hivyo kusema.
Hivyo utaratibu wa shughuli hapa ni kwenda kuwa muhimu.
>> Kufanya hii inaweza mimi kuiba, kusema, watu sita.
Na hebu angalia kama hatuwezi kufanya hii kuibua badala ya kanuni ya-busara.
Na tuna baadhi ya dhiki lovely mipira kwa leo.
OK, vipi kuhusu moja, mbili, katika nyuma - tarehe ya mwisho huko.
tatu, nne, wote wewe guys juu ya mwisho.
Na tano, sita.
Uhakika.
Tano na sita.
Yote ya haki na tutaweza kuja kwa nyie wakati ujao.
Haki wote, kuja juu juu.
>> Haki zote, tangu uko hapa juu ya kwanza, ungependa kuwa mmoja awkwardly
katika kioo Google hapa?
Haki ya wote, hivyo, OK, kioo, kurekodi video.
OK, wewe ni vizuri kwenda.
>> Haki wote, hivyo kama wewe guys unaweza kuja juu hapa, mimi tayari mapema
baadhi ya namba.
Haki wote, kuja juu zaidi ya hapa.
Na kwa nini wewe kwenda kidogo zaidi kwamba njia.
Na hebu angalia, nini jina lako, na kioo Google?
>> MWANAFUNZI: Ben.
>> SPIKA 1: Ben?
OK, Ben, utakuwa wa kwanza, literally.
Hivyo sisi ni kwenda kukutumia hadi mwisho wa hatua.
Haki ya wote, na jina lako?
>> MWANAFUNZI: Jason.
>> SPIKA 1: Yasoni, OK utasikia kuwa idadi tisa.
Hivyo kama unataka kufuata Ben njia hiyo.
>> MWANAFUNZI: Jill.
>> SPIKA 1: Jill, wewe ni kwenda kuwa 17, ambayo kama ningependa jambo hili zaidi
akili, mimi ingekuwa ilianza saa nyingine ya mwisho.
Kwenda njia hiyo.
22.
Na wewe ni?
>> MWANAFUNZI: Maria.
>> SPIKA 1: Maria, wewe utakuwa na 22.
Na jina lako ni nani?
>> MWANAFUNZI: Chris.
>> SPIKA 1: Chris, wewe utakuwa na 26.
Na kisha mwishowe.
>> MWANAFUNZI: Diana.
>> SPIKA 1: Diana, wewe utakuwa na 34.
Hivyo kuja juu zaidi ya hapa.
>> Haki ya wote, hivyo kukamilisha sorted kuamuru tayari.
Na hebu kwenda mbele na kufanya hii ili tuweze kweli -
Ben wewe ni aina tu ya kuangalia nje katika mahali pa huko.
OK, hivyo hebu kwenda mbele na depict hii kutumia silaha, kiasi kama mimi nilikuwa, hasa,
nini kinaendelea.
Hivyo kwenda mbele na kutoa nafsi zenu mguu au mbili kati yenu.
Na kwenda mbele na uhakika na mmoja mkono kwa anaye wewe lazima akionyesha
msingi huu.
Na kama wewe ni null tu kumweka moja kwa moja chini ya sakafu.
OK, hivyo nzuri.
>> Basi sasa tuna orodha wanaohusishwa, na napenda kupendekeza kwamba mimi itabidi kucheza nafasi ya
PTR, hivyo mimi si bother kubeba hii kote.
Na kisha - mtu kijinga mkataba - unaweza kuita hii kitu chochote unataka -
mtangulizi pointer, pred pointer -
ni tu jina la utani sisi alitoa katika sampuli zetu kanuni na mkono wangu wa kushoto.
upande mwingine kwamba kwenda na kuweka wimbo wa nani ni nani katika
kufuatia matukio.
>> Hivyo tuseme, kwanza, nataka konoa kwamba mfano wa kwanza wa kuingiza, kusema
20, katika orodha.
Hivyo nina kwenda haja ya mtu uliopo namba 20 kwa ajili yetu.
Hivyo mimi haja ya mtu malloc kutoka kwa watazamaji.
Kuja juu juu.
Nini jina lako?
>> MWANAFUNZI: Brian.
>> SPIKA 1: Brian, haki ya wote, hivyo atakuwa nodi zenye 20.
Haki wote, kuja juu zaidi ya hapa.
Na ni wazi, ambapo haina Brian ni mali?
Hivyo, katikati ya - kweli, kusubiri dakika.
Sisi ni kufanya hii nje ya utaratibu.
Sisi ni kufanya hii vigumu sana kuliko mahitaji kwa kuwa saa ya kwanza.
OK, tunakwenda bure Brian na realloc Brian kama tano.
>> OK, hivyo sasa tunataka kuingiza Brian kama tano.
Hivyo kuja juu juu hapa karibu na Ben kwa muda tu.
Na unaweza kuwaambia labda ambapo hadithi hii ni kwenda.
Lakini hebu kufikiri kwa makini kuhusu utaratibu wa shughuli.
Na ni just hii Visual hiyo ni kwenda kujipanga
na kwamba kanuni ya sampuli.
Hivyo hapa mimi PTR akizungumzia awali si wakati Ben, per se, lakini katika kila
thamani yeye ina, ambayo katika kesi hii ni - nini jina lako tena?
>> MWANAFUNZI: Jason.
>> SPIKA 1: Jason, hivyo wote Ben na mimi ni akionyesha Jason katika wakati huu.
Hivyo sasa mimi na kuamua, ambapo gani Brian ni mali?
Hivyo kitu pekee mimi kupata sasa hivi ni yake n data bidhaa.
Hivyo nina kwenda kuangalia, ni Brian chini ya Jason?
Jibu ni kweli.
>> Basi nini sasa mahitaji ya kutokea, katika mpangilio sahihi?
Mimi haja ya update kuyatumia jinsi wengi kwa jumla katika hadithi hii?
Ambapo mkono wangu bado ni akionyesha Yasoni, na mkono wako - kama unataka
kuweka mkono wako kama, aina ya, mimi sijui, alama ya swali.
OK, nzuri.
>> Haki ya wote, hivyo kuwa wagombea wachache.
Ama Ben au mimi au Brian au Jason au kila mtu mwingine, ambayo
kuyatumia haja ya mabadiliko?
Wangapi katika jumla?
>> OK, hivyo mbili.
Pointer yangu kweli haina jambo tena kwa sababu mimi nina tu ya muda mfupi.
Hivyo ni haya guys mbili, labda, wote Ben na Brian.
Hivyo basi mimi kupendekeza kwamba sisi update Ben, tangu yeye kwanza.
kipengele kwanza ya orodha hii sasa ni kwenda kuwa Brian.
Hivyo Ben mchemko ifikapo Brian.
OK, sasa nini?
>> Ambaye anapata alisema saa nani?
>> MWANAFUNZI: [inaudible].
>> SPIKA 1: OK hivyo Brian ana kwa uhakika katika Jason.
Lakini mimi waliopotea track ya pointer kwamba?
Sijui ambapo Jason ni?
>> MWANAFUNZI: [inaudible].
>> SPIKA 1: mimi kufanya, tangu mimi nina pointer ya muda mfupi.
Na labda, mimi si iliyopita kwa kumweka kwenye nodi mpya.
Hivyo tunaweza tu na Brian hatua saa yeyote nina akionyesha.
Na sisi ni kosa.
Hivyo kesi moja, kuingizwa katika mwanzo wa orodha.
Kulikuwa hatua mbili muhimu.
Moja, tuna update Ben, na kisha sisi pia kuwa na update Brian.
Na kisha mimi hawana bother traipsing njia ya mapumziko ya
orodha, kwa sababu sisi tayari kupatikana yake mahali, kwa sababu yeye ni mali ya
kushoto wa kipengele kwanza.
>> Haki ya wote, hivyo pretty moja kwa moja.
Kwa kweli, anahisi kama tuko karibu kufanya hii ngumu sana.
Basi hebu sasa konoa mwisho ya orodha, na kuona ambapo
utata kuanza.
Hivyo kama sasa, mimi alloc kutoka kwa watazamaji.
Mtu yeyote unataka kucheza 55?
Haki zote, niliona mkono wako wa kwanza.
Kuja juu juu.
Yeah.
Nini jina lako?
>> MWANAFUNZI: [inaudible].
>> SPIKA 1: Habata.
OK, kuja juu juu.
Wewe utakuwa na simu 55.
Hivyo, bila shaka, ni mali mwisho wa orodha.
Basi hebu Replay simulation na mimi kuwa PTR kwa muda tu.
Hivyo nina uhakika kwanza kwenda katika chochote Ben ni akionyesha.
Tuko wote akizungumzia sasa saa Brian.
Hivyo 55 ni si chini ya watano.
Hivyo nina kwenda kwa update mwenyewe kwa akizungumzia pointer Brian ijayo, ambao
sasa ni mwendo wa Jason.
55 ni si chini ya tisa, hivyo Mimi nina kwenda update PTR.
Mimi nina kwenda update PTR Mimi kwenda update PTR.
Na mimi naenda - hmm, nini jina yako tena?
>> MWANAFUNZI: Diana.
>> SPIKA 1: Diana ni akizungumzia, bila shaka, saa null kwa mkono wake wa kushoto.
Hivyo ambapo gani Habata kweli ni wazi?
Kwa upande wa kushoto, hapa.
Hivyo ni jinsi gani mimi kujua kuweka wake Hapa Nadhani nimepata Star up.
Kwa sababu ni nini PTR sanaa huu katika muda?
Null.
Hivyo hata kama, kuibua, tunaweza wazi kuona yote haya
guys hapa juu ya hatua.
Nimekuwa si naendelea wimbo wa uliopita mtu katika orodha.
Sina kidole kuonyesha nje, katika kesi hii, idadi nodi 34.
>> Basi hebu kweli kuanza hii zaidi.
Hivyo sasa mimi kwa kweli kufanya haja pili mitaa kutofautiana.
Na hii ni nini utaona katika halisi sampuli C kanuni, ambapo kama mimi kwenda,
wakati mimi update mkono wangu wa kulia kwa uhakika Jason, na hivyo kuacha Brian nyuma, mimi
bora kuanza kutumia mkono wangu wa kushoto kwa update ambapo nilikuwa, ili kama mimi kwenda
kupitia orodha hii -
zaidi kuliko mimi nia awkwardly sasa hapa kuibua -
Mimi nina kwenda kupata mwisho wa orodha.
>> Mkono hii bado ni null, ambayo ni pretty haina maana, zaidi ya kuonyesha
Mimi nina wazi mwisho wa orodha, lakini sasa angalau nina hii
mtangulizi pointer akizungumzia hapa, hivyo sasa nini mikono na nini kuyatumia haja
kuwa updated?
Ambaye mkono unataka reconfigure kwanza?
>> MWANAFUNZI: [inaudible].
>> SPIKA 1: OK, hivyo Diana.
Ambapo unataka uhakika Diana kushoto pointer saa?
Saa 55, labda, ili kwamba tumekuwa kuingizwa huko.
Na ambapo wanapaswa 55 pointer kwenda?
Chini, anayewakilisha null.
Na mikono yangu, katika hatua hii, wala jambo kwa sababu walikuwa tu
muda vigezo.
Hivyo sasa sisi ni kosa.
>> Hivyo utata ziada hapo - na siyo kwamba ni vigumu kutekeleza,
lakini tunahitaji kutofautiana sekondari ya kufanya uhakika kwamba kabla mimi hoja haki yangu
mkono, mimi update thamani ya kushoto yangu mkono, pred pointer katika kesi hii, hivyo
kwamba nina pointer trailing kuweka wimbo wa wapi nilipo.
Sasa kama kando, kama wewe ni kufikiri hii kupitia, hii anahisi kama ni
kidogo annoying kuwa na kuweka wimbo wa mkono huo wa kushoto.
>> Gani ufumbuzi mwingine wa tatizo hili wamekuwa?
Kama got wa kuunda upya data muundo tunazungumzia
kupitia hivi sasa?
Kama aina hii tu ya anahisi kidogo annoying kuwa, kama, mbili kuyatumia
kwenda kupitia orodha, nani mwingine anaweza kuwa, katika ulimwengu halisi, iimarishwe
habari kwamba tunahitaji?
Yeah?
>> MWANAFUNZI: [inaudible].
>> SPIKA 1: Hasa.
Haki hivyo kuna kweli ya kuvutia kijidudu ya wazo.
Na hili wazo la pointer uliopita, akionyesha kipengele uliopita.
Nini kama mimi tu ilivyo kwamba ndani ya orodha yenyewe?
Na ni kwenda kuwa ngumu kwa taswira huu bila ya karatasi kila
kuanguka kwa sakafu.
Lakini tuseme kwamba hawa guys kutumika wote ya mikono yao ya kuwa uliopita
pointer, na pointer ijayo, na hivyo kutekeleza kile Tutamwita doubly
wanaohusishwa orodha.
Hiyo naomba aina ya rewind, kwa urahisi zaidi bila mimi,
programu, baada ya kuweka kufuatilia manually -
kweli manually -
ya ambapo mimi alikuwa hapo awali katika orodha.
Hivyo sisi si kufanya hivyo.
Tutaweza kushika ni rahisi kwa sababu hiyo ni yatakuja kwa bei, mara mbili kama
mengi nafasi kwa ajili ya kuyatumia, kama unataka moja ya pili.
Lakini hiyo ni kweli ya kawaida data muundo inajulikana kama
doubly wanaohusishwa orodha.
>> Hebu kufanya mfano wa mwisho hapa na kuweka haya guys nje ya taabu yao.
Hivyo malloc 20.
Kuja juu juu kutoka aisle huko.
Haki zote, nini jina lako?
>> MWANAFUNZI: [inaudible].
>> SPIKA 1: Samahani?
>> MWANAFUNZI: [inaudible].
>> SPIKA 1: Demeron?
OK kuja juu juu.
Mtakuwa 20.
Wewe ni wazi ni kwenda ni kati ya 17 na 22.
Hivyo basi mimi kujifunza somo yangu.
Mimi naenda kuanza pointer akionyesha Brian.
Na mimi nina kwenda kuwa na mkono wangu wa kushoto tu update kwa Brian kama mimi hoja ya
Jason, kuangalia anafanya 20 chini ya tisa?
No
Ni 20 chini ya 17?
No
Ni 20 chini ya 22?
Ndiyo.
Hivyo kile kuyatumia au mikono haja ya kubadili ambapo wao ni akizungumzia sasa?
>> Hivyo tunaweza kufanya 17 akionyesha 20.
Hivyo kwamba ni faini.
Wapi tunataka uhakika pointer yako sasa?
Saa 22.
Na tunajua ambapo 22 ni, tena shukrani pointer yangu ya muda mfupi.
Hivyo sisi ni OK huko.
Hivyo kwa sababu ya hii ya kuhifadhi muda Nimekuwa naendelea wimbo wa ambapo kila mtu ni.
Na sasa unaweza kwenda katika kuibua ambapo wewe ni mali, na sasa tunahitaji 1, 2, 3,
4, 5, 6, 7, 8, 9 dhiki mipira, na pande zote ya applause kwa
haya guys, kama tunaweza.
Nicely kufanyika.
>> [Makofi]
>> SPIKA 1: zote haki.
Na unaweza kuweka vipande ya karatasi kama mementos.
>> Haki ya wote, hivyo, imani yangu ni mengi rahisi kutembea kwa njia ya kwamba pamoja na
binadamu zaidi ni pamoja na kanuni halisi.
Lakini nini utapata katika muda tu sasa, ni kwamba huo - oh, asante.
Asante -
ni kwamba utapata kwamba data huo muundo, orodha wanaohusishwa, unaweza kweli
kutumika kama kuzuia ujenzi na hata zaidi kisasa data miundo.
>> Na kutambua pia mandhari hapa ni kwamba tumekuwa kabisa ilianzisha zaidi
utata katika utekelezaji ya algorithm hii.
Kuingizwa, na kama sisi akaenda kwa njia hiyo, kufuta na kutafuta, ni kidogo
ngumu zaidi kuliko alikuwa pamoja na safu.
Lakini sisi kupata baadhi ya mabadiliko.
Sisi kupata adaptive data muundo.
>> Lakini tena, sisi kulipa bei ya kuwa na baadhi ya ziada utata, katika
kutekeleza hilo.
Na sisi ni kupewa upatikanaji random.
Na kwa kuwa waaminifu, kuna si baadhi nice safi slide naweza kukupa kwamba
anasema hapa ni kwa nini orodha wanaohusishwa ni bora kuliko safu.
Na kuondoka saa hiyo.
Kwa sababu mandhari reoccurring sasa, hata zaidi ya hivyo katika wiki ijayo, ni
kwamba kuna si lazima jibu sahihi.
>> Hii ni kwa nini tuna mhimili tofauti ya kubuni kwa seti tatizo.
Itakuwa sana mazingira nyeti kama unataka kutumia data hii
muundo au kwamba mmoja, na itakuwa itategemea kile mambo na wewe katika suala
wa rasilimali na utata.
>> Lakini basi mimi kupendekeza kwamba data bora muundo, grail takatifu, itakuwa
kitu ambacho ni mara kwa mara wakati, bila kujali jinsi mambo mengi ni
ndani yake, si ingekuwa ajabu ikiwa data muundo akarudi majibu katika
mara kwa mara wakati.
Ndiyo.
Hii neno ni katika kamusi yako kubwa.
Au hakuna, hii si neno.
Au tatizo lolote vile huko.
Naam hebu angalia kama hatuwezi angalau kuchukua hatua kuelekea hiyo.
>> Basi mimi kupendekeza mpya data muundo kwamba inaweza kutumika kwa ajili ya mambo mbalimbali,
katika kesi hii inaitwa meza hash.
Na hivyo sisi ni kweli nyuma ya glancing katika safu, katika kesi hii, na
kiasi fulani kiholela, nimekuwa inayotolewa hii hash meza kama safu na aina ya
mbili-dimensional safu -
au tuseme ni taswira ya hapa kama mbili dimensional safu - lakini hii ni
safu ya ukubwa 26, vile kwamba kama sisi piga meza safu, meza bracket
sifuri ni Mstatili kwa juu.
Meza bracket 25 ni mstatili chini.
Na hii ni jinsi mimi ili kuteka data muundo ambayo mimi unataka kuhifadhi
watu majina.
>> Hivyo kwa mfano, na mimi si kuteka nzima kitu hapa juu ya uendeshaji, kama mimi
alikuwa na safu hii, ambayo mimi sasa kwenda piga meza hash, na hii ni tena
eneo sifuri.
Hii hapa ni mahali mmoja, na kadhalika.
Mimi kudai kwamba mimi nataka kutumia data hii muundo, kwa ajili ya majadiliano,
kuhifadhi majina ya watu, Alice na Bob na Charlie na majina mengine kama hayo.
Hivyo kufikiri ya hii sasa kama mwanzo ya, kusema, kamusi
kwa kura ya maneno.
Wao kutokea kwa kuwa majina katika mfano wetu hapa.
Na hii yote ni pia germane, pengine, kwa kutekeleza kusahihisha Spell, kama sisi
ili kwa tatizo kuweka sita.
>> Hivyo kama tuna safu ya kawaida ya jumla 26 hivyo kwamba hii ni mahali 25
chini, na mimi kudai kwamba Alice ni neno la kwanza katika kamusi ya
majina ya kwamba mimi nataka kuingiza ndani ya RAM, ndani ya muundo huu data, ambapo ni
silika kuwaambia kwamba Alice jina lazima kwenda katika safu hii?
>> Tuna njia 26.
Ambapo tunataka kuweka wake?
Tunataka yake katika mabano sifuri, haki?
kwa Alice, hebu wito kwamba sifuri.
Na B itakuwa moja, na C itakuwa mbili.
Hivyo sisi ni kwenda kuandika Jina Alice hapa juu.
Kama sisi kisha kuingiza Bob, wake jina kwenda hapa.
Charlie kwenda hapa.
Na kadhalika chini kupitia muundo huu data.
>> Hii ni ajabu data muundo.
Kwa nini?
Vizuri ni nini wakati mbio ya kuingiza jina binadamu ndani ya hii
data muundo hivi sasa?
Kutokana na kwamba meza hii ni kutekelezwa, kweli, kama safu.
Naam ni mara kwa mara wakati.
Ni utaratibu wa moja.
Kwa nini?
>> Vizuri jinsi gani unaweza kuamua ambapo Alice ni mali?
Ukiangalia ambayo barua ya jina lake?
kwanza.
Na unaweza kupata huko, kama ni kamba, na kuangalia tu kamba
bracket sifuri.
Hivyo tabia 0 wa kamba.
Hiyo ni rahisi.
Sisi gani kwamba katika crypto zoezi wiki iliyopita.
Na kisha mara moja, unajua kwamba Alice mbili ni mji mkuu, tunaweza Ondoa
mbali ya 65 au mji mkuu yenyewe, ambayo inatupa sifuri.
Hivyo sisi sasa tunajua kuwa ni mali ya Alice katika eneo sifuri.
>> Na kupewa pointer data hii muundo, wa aina fulani, jinsi muda gani
ni kuchukua yangu ya kupata eneo sifuri katika safu?
Hatua moja tu, haki Ni mara kwa mara wakati sababu ya kupata random sisi
mapendekezo ilikuwa kipengele wa safu.
Hivyo katika muda mfupi, kuhesabia nje nini index jina la Alice ni, ambayo ni, katika
kesi hii, ni, au hebu tu kutatua kwamba kwa sifuri, ambapo ni moja B na C ni
mbili, kuhesabia kwamba nje ni mara kwa mara wakati.
Mimi tu na kuangalia barua yake ya kwanza, kuhesabia ambapo sifuri ni
safu pia ni mara kwa mara wakati.
Basi kitaalam kwamba kama hatua mbili sasa.
Lakini hiyo bado mara kwa mara.
Hivyo tunatoa wito kwamba O kubwa ya moja, hivyo tumekuwa Alice kuingizwa katika meza hii katika
mara kwa mara wakati.
>> Lakini kwa kweli, mimi nina kuwa naive hapa, sawa?
Nini kama kuna Haruni katika darasa?
Au Alicia?
Au majina mengine ya kuanzia na A. wapi sisi kwenda kuweka
kwamba mtu, haki?
I mean, hivi sasa kuna tatu tu watu juu ya meza, hivyo labda sisi
wanapaswa kuweka Haruni katika eneo sifuri moja mbili tatu.
>> Haki, mimi naweza kuweka hapa.
Lakini basi, kama sisi kujaribu kuingiza Daudi katika orodha hii, ambapo gani Daudi kwenda?
Sasa mfumo wetu kuanza kuvunja chini, sawa?
Kwa sababu sasa Daudi kuishia hapa kama Haruni ni kweli hapa.
Na hivyo sasa hii dhana nzima ya kuwa na safi data muundo kwamba inatupa
mara kwa mara wakati insertions ni tena mara kwa mara wakati, kwa sababu mimi
kuangalia, oh, damnit, mtu tayari ni katika eneo Alice.
>> Hebu kuchunguza wengine wa data hii muundo, kuangalia kwa doa kuweka
mtu kama jina la Haruni.
Na hivyo kuwa pia ni kuanzia kuchukua muda linear.
Aidha, kama wewe sasa unataka kupata Haruni katika muundo huu data, na wewe
kuangalia, na jina la Haruni si hapa.
Kimsingi, ungekuwa tu kusema Haruni si katika muundo wa data.
Lakini kama wewe kufanya kuanza kufanya chumba kwa ajili ya Haruni ambapo kuna lazima wamekuwa D
au E, wewe, kesi mbaya, na kuangalia nzima data muundo, katika
kesi ambayo ni warithi katika kitu linear katika ukubwa wa meza.
>> Hivyo haki ya wote, mimi itabidi kurekebisha hii.
Tatizo hapa ni kwamba nilikuwa 26 vipengele katika safu hii.
Hebu mabadiliko hayo.
Whoops.
Hebu mabadiliko hayo ili badala ya kuwa kawaida 26 kwa jumla, taarifa ya chini
index ni kwenda na mabadiliko kwa n bala 1.
Kama 26 ni wazi ndogo mno kwa 'binadamu majina, kwa sababu kuna maelfu ya
majina ya dunia, hebu tu kufanya katika 100 au 1,000 au 10,000.
Hebu tu kutenga mengi zaidi nafasi.
>> Vizuri kwamba siyo lazima kupungua uwezekano kwamba hatutakuwa na mbili
watu wenye majina kuanzia na, na hivyo, walikuwa kwenda kujaribu kuweka
majina katika sifuri eneo bado.
Wao bado uko kwenda yanapogongana, ambayo ina maana bado tunahitaji ufumbuzi wa kuweka
Alice na Haruni na Alicia na nyingine majina kuanzia na mahali pengine.
Lakini ni kiasi gani cha tatizo ni hii?
Nini uwezekano kwamba wewe kuwa na migongano katika data
muundo kama hii?
>> Vizuri, basi mimi - tutaweza kurudi kwa swali hapa.
Na kuangalia jinsi gani tupate kutatua hilo kwanza.
Hebu vuta hadi pendekezo hili hapa.
Nini sisi tu ilivyoelezwa ni algorithm, heuristic kuitwa linear
uchunguzi ambapo, kama walijaribu kuingiza kitu hapa katika data hii
muundo, ambayo inaitwa meza hash, na kuna chumba hakuna huko,
kweli kuchunguza muundo wa data kuangalia, ni hii inapatikana?
Je, hii ni Available hii inapatikana?
Ni hii inapatikana?
Na wakati hatimaye ni, wewe kuingiza jina kwamba awali lengo
mahali pengine katika eneo hilo.
Lakini katika hali mbaya zaidi, doa tu ili kuwa chini kabisa ya data
muundo, mwisho wa safu.
>> Hivyo linear uchunguzi, katika hali mbaya zaidi, warithi katika algorithm linear ambapo
Haruni, kama yeye hufanyika kuwa na kuingizwa mwisho katika muundo huu data, apate
collide na eneo hili kwanza, lakini kisha mwisho kwa bahati mbaya mwishoni sana.
Hivyo hii si mara kwa mara wakati takatifu grail kwa ajili yetu.
Mbinu hii ya mambo ya ndani ya kuingiza muundo wa data kuitwa hash
meza haionekani kuwa mara kwa mara wakati angalau si katika kesi ujumla.
Ni wanaweza kukabidhi katika kitu linear.
>> Basi nini kama sisi kutatua migongano kiasi fulani tofauti?
Hivyo hapa ni ya kisasa zaidi mbinu nini bado
kuitwa meza hash.
Na kwa hash, kama kando, nini I mean ni index kwamba
Mimi inajulikana mapema.
Kwa kitu hash unaweza kuwa mawazo ya kama kitenzi.
>> Hivyo kama wewe Alice hash ni jina, kazi hash, hivyo kusema,
wanapaswa kurudi idadi.
Katika kesi hii ni sifuri kama yeye ni katika eneo sifuri, moja ikiwa yeye ni saa
eneo moja, na kadhalika.
Hivyo kazi yangu hash hivi sasa imekuwa super rahisi, tu kuangalia
barua ya kwanza kwa jina la mtu.
Lakini kazi hash inachukua kama pembejeo baadhi ya kipande cha data,
kamba, int, chochote.
Na ni mtemi nje kwa kawaida idadi.
Na kwamba idadi hiyo ni wapi kwamba data kipengele ni katika muundo wa data
inajulikana hapa kama meza hash.
>> Hivyo tu intuitively, hii ni tofauti kidogo mazingira.
Hii kweli ni akimaanisha mfano kuwashirikisha siku za kuzaliwa, ambapo
huenda kuna wengi kama Siku 31 katika mwezi.
Lakini ni nini mtu huyu kuamua kufanya katika tukio la mgongano?
Muktadha sasa kuwa, si mgongano wa majina, lakini mgongano wa siku za kuzaliwa,
kama watu wawili na kuzaliwa sawa juu ya Oktoba 2, kwa mfano.
>> MWANAFUNZI: [inaudible].
>> SPIKA 1: Yeah, hivyo hapa tuna leveraging ya orodha wanaohusishwa.
Hivyo inaonekana tofauti kidogo kuliko sisi akauchomoa mapema.
Lakini sisi kuonekana kuwa na safu upande wa kushoto.
Hiyo ni moja index, kwa maana hakuna Hasa sababu.
Lakini bado ni safu.
Ni safu ya kuyatumia.
Na kila moja ya mambo hayo, kila mmoja haya duru au milalo - kufyeka
anayewakilisha null - kila moja ya haya kuyatumia ni inaonekana akizungumzia
nini data muundo?
orodha wanaohusishwa.
>> Hivyo basi, tuna uwezo wa ngumu kificho katika mpango wetu
ukubwa wa meza.
Katika kesi hiyo, tunajua kuna kamwe zaidi ya siku 31 kwa mwezi.
Hivyo ngumu coding thamani kama 31 ni kuridhisha katika mazingira.
Katika mazingira ya majina, ngumu coding 26 si ya maana ni watu
majina tu kuanza na, kwa mfano, alfabeti kuwashirikisha kupitia Z.
>> Tunaweza cram wote ndani ya data kwamba muundo wa muda mrefu kama, wakati sisi kupata
mgongano, hatuwezi kuweka majina hapa, sisi badala kufikiri ya seli hizi
si kama masharti wenyewe, lakini kama kuyatumia kwa, kwa mfano, Alice.
Na kisha Alice unaweza kuwa mwingine pointer kwa jina la mtu mwingine kwa kuanzia na
A. Na Bob kweli inakwenda zaidi ya hapa.
>> Na kama kuna mwingine jina kuanzia na B, yeye mwisho juu zaidi ya hapa.
Na hivyo kila mmoja wa mambo ya hii meza mbili, kama sisi iliyoundwa hii
zaidi kidogo cleverly -
kuja juu -
kama sisi iliyoundwa hii zaidi kidogo cleverly, sasa inakuwa data adaptive
muundo, ambapo hakuna kikomo kwa bidii juu ya jinsi mambo mengi unaweza kuingiza
ndani yake kwa sababu kama una mgongano, hiyo faini.
Tu kwenda mbele na append kwa yale tuliona kidogo iliyopita alikuwa
inayojulikana kama orodha wanaohusishwa.
>> Naam hebu pause kwa muda tu.
Je, ni uwezekano wa mgongano katika nafasi ya kwanza?
Haki, labda mimi nina zaidi ya kufikiri, labda Nina zaidi ya uhandisi na tatizo hili,
kwa sababu unajua nini?
Ndiyo, naweza kuja na holela mifano mbali juu ya kichwa yangu kama
Allison na Haruni, lakini katika hali halisi, aliyopewa usambazaji sare ya
pembejeo, kwamba ni baadhi ya insertions random katika muundo wa data, kile kwa kweli ni
uwezekano wa mgongano?
Vizuri zamu nje, ni kweli super juu.
Hebu kujumlisha hii Tatizo ni kama hii.
>> Hivyo katika chumba ya n CS50 wanafunzi, nini uwezekano kwamba angalau
wanafunzi wawili katika chumba kuwa kuzaliwa sawa?
Hivyo kuna nini. Hund wachache -
200, 300 watu hapa na kadhaa mia watu nyumbani leo.
Hivyo kama alitaka tujiulize nini uwezekano wa watu wawili
katika chumba kuwa siku ya kuzaliwa huo, tunaweza takwimu hii nje.
Na mimi kudai kweli kuna mambo mawili watu na kuzaliwa sawa.
>> Kwa mfano, haina mtu yeyote kuwa na siku ya kuzaliwa leo?
Jana?
Kesho?
Haki wote, hivyo ni anahisi kama mimi nina kwenda kwa kuwa kufanya hivyo 363 au hivyo zaidi
mara kwa kweli kufikiri kama sisi kufanya kuwa na mgongano.
Au sisi inaweza tu kufanya hivyo kihisabati badala ya tediously
kufanya hivyo.
Na kupendekeza yafuatayo.
>> Hivyo napendekeza kwamba tunaweza kubuni uwezekano wa watu wawili
huo siku ya kuzaliwa kama uwezekano wa 1 bala uwezekano wa mtu kuwa na
kuzaliwa sawa.
Hivyo kupata hii, na hii ni dhana njia ya kuandika hii, kwa
mtu wa kwanza katika chumba, yeye au yeye unaweza kuwa na mtu yeyote wa inawezekana
kuzaliwa kuchukua siku 365 kwa mwaka, pamoja na msamaha kwa watu wenye
Februari 29 siku ya kuzaliwa.
>> Hivyo mtu wa kwanza katika chumba hiki ni bure kuwa na idadi yoyote ya siku za kuzaliwa
nje ya uwezekano 365 ili tutaweza kufanya hivyo 365 kugawanywa na 365,
ambayo ni moja.
mtu wa pili katika chumba, kama lengo ni kuepuka mgongano, unaweza tu
kuwa na wake au kuzaliwa kwake juu ya jinsi ya nyingi tofauti inawezekana siku?
364.
Hivyo awamu ya pili katika msemo huu ni kimsingi kufanya kwamba math kwa ajili yetu
kwa kutoa off moja inawezekana siku.
Na kisha siku ya pili, siku ya pili, siku ya pili chini ya idadi ya jumla
ya watu katika chumba.
>> Na kama sisi kisha kufikiria, nini basi ni uwezekano si ya kila mtu kuwa
kipekee siku za kuzaliwa, lakini tena 1 bala kwamba, nini sisi kupata ni usemi
ambayo inaweza sana fancifully kuangalia kama hii.
Lakini ni zaidi ya kuvutia kuangalia kuibua.
Hii ni chati ambapo kwenye mhimili x-ni idadi ya watu katika chumba,
idadi ya siku za kuzaliwa.
Kwenye mhimili y-uwezekano wa mgongano, watu wawili
baada ya kuzaliwa sawa.
>> Na takeaway kutoka Curve hii ni kwamba haraka kama wewe kupata kama 40
wanafunzi, uko uwezekano hadi saa 90% combinatorically wa mbili
watu au zaidi baada ya kuzaliwa sawa.
Na mara moja kupata kama watu 58 ni karibu asilimia 100% ya nafasi mbili
watu katika chumba ni kwenda na kuzaliwa sawa, hata kama kuna
365 au 366 ndoo inawezekana, na 58 tu ya watu katika chumba hicho.
Tu kitakwimu uko uwezekano wa kupata migongano, ambayo katika muda mfupi
kilichomsukuma mjadala huu.
Kwamba hata kama sisi kupata dhana hapa, na kuanza kuwa na minyororo ya haya, bado tuko
kwenda na migongano.
>> Hivyo kwamba anaomba swali, ni nini gharama ya kufanya insertions na kufuta maneno
katika muundo wa data kama hii?
Vizuri basi mimi kupendekeza -
na napenda kwenda nyuma ya screen juu ya hapa - kama sisi n vipengele katika
orodha, hivyo kama sisi ni kujaribu kuingiza n vipengele, na tuna
wangapi taarifa ndoo?
Hebu sema 31 ndoo taarifa katika kesi ya siku za kuzaliwa.
Nini upeo wa urefu wa moja ya haya minyororo uwezekano?
>> Kama tena kuna 31 inawezekana kuzaliwa katika mwezi huo.
Na tuko tu clumping kila mtu -
kweli kwamba ni mfano wa kijinga.
Hebu kufanya 26 badala yake.
Hivyo kama kweli kuwa watu ambao majina kuanza na kupitia Z, na hivyo kutoa
sisi 26 uwezekano.
Na sisi ni kutumia mfumo wa data kama mmoja sisi tu kuona, ambapo tuna
safu ya kuyatumia, ambayo kila mmoja pointi kwa orodha wanaohusishwa ambapo
orodha ya kwanza ni ya kila mtu na Alice jina.
orodha ya pili ni kila na jina kwa kuanzia na, kuanzia
na B, na kadhalika.
>> Nini urefu uwezekano wa kila moja ya wale orodha kama sisi kudhani safi nzuri
usambazaji wa majina kupitia Z hela mfumo mzima data?
Kuna n watu katika muundo data kugawanywa na 26, kama uko nicely
kuenea nje zaidi ya yote data muundo.
Hivyo urefu wa kila moja ya haya minyororo ni n kugawanywa na 26.
Lakini katika nukuu kubwa O, ni nini?
Nini ni kwamba kweli?
Hivyo ni kweli tu n, haki?
Kwa sababu tumekuwa alisema katika siku za nyuma, kwamba ugh kugawanya na 26.
Ndiyo, katika hali halisi ni kasi zaidi.
Lakini katika nadharia, siyo kimsingi yote kwa kasi zaidi.
>> Hivyo hatuna wanaonekana kuwa kiasi kwamba wote karibu na hii grail takatifu.
Kwa kweli, hii ni linear wakati.
Heck, katika hatua hii, kwa nini sio sisi tu kutumia moja kubwa wanaohusishwa orodha?
Mbona sisi tu kutumia moja kubwa safu ya kuhifadhi majina ya
kila mtu katika chumba?
Vizuri, bado kuna kitu kulazimisha juu ya meza hash?
Je, bado kuna kitu kulazimisha kuhusu muundo data
kwamba inaonekana kama hii?
Hii.
>> MWANAFUNZI: [inaudible].
>> SPIKA 1: Haki, na tena kama ni tu linear wakati algorithm, na
linear wakati data muundo, kwa nini si mimi tu kuhifadhi jina la kila mtu katika kubwa
safu, au katika orodha kubwa wanaohusishwa?
Na kuacha kufanya hivyo CS vigumu sana kuliko mahitaji kwa kuwa?
Je, ni kulazimisha kuhusu hili, hata ingawa mimi kukwangua nje?
>> MWANAFUNZI: [inaudible].
>> SPIKA 1: insertions siyo?
Ghali tena.
Hivyo insertions uwezekano bado nilikuwa kuwa mara kwa mara wakati, hata kama wako data
muundo inaonekana kama hii, safu ya kuyatumia, ambayo kila mmoja ananyoosha katika
uwezekano wa orodha wanaohusishwa.
Jinsi gani unaweza kufikia mara kwa mara wakati kuingizwa ya majina?
Fimbo yake mbele, haki?
>> Kama sisi sadaka lengo kubuni kutoka mapema, ambapo sisi alitaka kuweka
jina la kila mtu, kwa mfano, namna, au wote wa idadi ya juu ya hatua sorted,
tuseme kwamba tuna zisizochambuliwa wanaohusishwa orodha.
Ni tu yanatugharimu hatua moja au mbili, kama katika kesi ya Ben na Brian
mapema, kuingiza kipengele katika mwanzo wa orodha.
Hivyo kama sisi hawajali kuhusu kuchagua kila ya majina kuanzia na au wote
majina kuanzia na B, tunaweza bado kufikia mara kwa mara wakati kuingizwa.
Sasa kuangalia juu Alice au Bob au jina lolote zaidi kwa ujumla bado ni nini?
Ni kubwa O ya n kugawanywa na 26, katika bora kesi ambapo kila mtu ni enhetligt
kusambazwa, ambapo kuna kama wengi wa kama kuna Z, ambayo pengine ni
unrealistic.
Lakini hiyo bado linear.
>> Lakini hapa, sisi kuja nyuma kwa uhakika ya nukuu asymptotic kuwa
kinadharia kweli.
Lakini katika ulimwengu wa kweli, kama mimi kudai kwamba mpango wangu anaweza kufanya kitu 26 mara
kasi zaidi kuliko yako, ambaye mpango ni wewe kwenda wanapendelea kutumia?
Wako au yangu, ambayo ni 26 mara kwa kasi?
Realistically, mtu ambaye ni 26 mara kwa kasi, hata kama kinadharia
algorithms wetu kukimbia katika huo asymptotic mbio wakati.
>> Basi mimi kupendekeza mbalimbali ufumbuzi kabisa.
Na kama hii haina pigo akili yako, tuko nje ya miundo ya data.
Hivyo hii ni trie -
aina ya jina kijinga.
Inakuja kutoka retrievals, na neno ni yameandikwa trie, t-r-i-e, kwa sababu ya
Bila shaka retrieval inaonekana kama trie.
Lakini hiyo ni historia trie ya neno.
>> Hivyo trie ni kweli baadhi ya aina ya mti, na pia ni kucheza kwenye neno hilo.
Na hata kama huwezi kabisa kuona na taswira hii, trie ni
mti muundo, kama mti familia na moja babu saa ya juu na kura
wajukuu na vitukuu kama majani juu ya chini.
Lakini kila nodi katika trie ni safu.
Na ni katika safu - na hebu oversimplify kwa sasa - ni
safu, katika kesi hii, ya ukubwa wa 26, ambapo kila node tena ni safu ya ukubwa
26, ambapo kipengele 0 kwa kuwa safu inawakilisha, na ya mwisho
kipengele katika kila vile safu inawakilisha Z.
>> Hivyo napendekeza, basi, kwamba hiki data muundo, unaojulikana kama trie, unaweza kuwa
kutumika pia kuhifadhi maneno.
Tuliona wakati iliyopita jinsi gani tunaweza kuhifadhi maneno, au katika majina ya kesi hii, na sisi
aliona mapema jinsi tunaweza kuhifadhi namba, lakini kama sisi kuzingatia majina au masharti
hapa, taarifa nini kuvutia.
Mimi kudai kwamba Maxwell jina ni ndani ya muundo huu data.
Ambapo unaona Maxwell?
>> MWANAFUNZI: [inaudible].
>> SPIKA 1: Upande wa kushoto.
Basi nini kuvutia na data hii muundo ni badala ya kuhifadhi
kamba ya M-A-X-W-E-L-L backslash sifuri, kila contiguously, nini badala kufanya
ni kufuatia.
Kama hii ni trie kama muundo data, kila aina ya nodi ambaye ni tena safu,
na unataka kuhifadhi Maxwell, wewe kwanza index na hivyo mzizi wa nodi, hivyo
kusema, nodi juu kabisa, katika eneo M, haki, hivyo
takribani katika katikati.
Na kisha kutoka huko, wewe kufuata pointer nodes mtoto, hivyo kusema.
Hivyo kwa mantiki familia mti, wewe kufuata ni kushuka.
Na kwamba kusababisha wewe nodi mwingine upande wa kushoto huko, ambayo ni
mwingine tu safu.
>> Na kisha kama unataka kuhifadhi Maxwell, unakuta pointer kwamba inawakilisha
, Ambayo ni hii moja hapa.
Basi wewe kwenda nodi ijayo.
Na ilani - hii ni kwa nini picha ya kudanganya kidogo -
nodi hii kuangalia super vidogo.
Lakini haki ya hii ni Y na Z. Ni tu mwandishi ina truncated
picha hivyo kwamba kweli kuona mambo.
Vinginevyo hii picha itakuwa hugely kote.
Hivyo sasa index katika eneo X, kisha W, Kisha E, basi L, kisha L. Kisha nini
hii udadisi?
>> Naam, kama sisi ni kutumia aina hii ya mpya kuchukua juu ya jinsi ya kuhifadhi kamba katika
data muundo, bado wanahitaji kimsingi kuangalia mbali katika data
muundo kwamba neno kuishia hapa.
Kwa maneno mengine, kila mmoja wa nodi hiyo namna fulani ana kukumbuka kwamba sisi
kweli ikifuatiwa yote ya kuyatumia haya na ni kuacha kidogo
mkate chembe chini ya hii hapa muundo zinaonyesha M-A-X-W-E-L-L ni
Hakika katika muundo huu data.
>> Hivyo tupate kufanya kazi hii kama ifuatavyo.
Kila wa nodi katika picha ya sisi tu msumeno ina moja, safu ya ukubwa 27.
Na ni sasa 27, kwa sababu katika p kuweka sita, tutaweza kweli kukupa apostrophe,
ili tuweze kuwa na majina kama O'Reilly na wengine na apostrophes.
Lakini huo wazo.
Kila moja ya mambo hayo katika safu pointi struct
nodi, hivyo tu nodi.
Hivyo hii ni kukumbusha ya orodha yetu ya wanaohusishwa.
>> Na kisha nina Boolean, ambayo mimi itabidi kuwaita neno, ambayo ni kwenda tu kuwa
kweli kama neno mwisho katika hii nodi katika mti.
Ni kwa ufanisi inawakilisha kidogo pembetatu tuliona wakati iliyopita.
Hivyo kama neno mwisho katika kwamba nodi katika mti, kwamba shamba neno itakuwa kweli,
ambayo ni conceptually kuangalia mbali, au sisi ni kuchora hii pembetatu, ndiyo kuna
ni neno hapa.
>> Hivyo hii ni trie.
Na sasa swali ni, nini ni yake mbio wakati?
Je, ni kubwa O ya n?
Je, ni kitu kingine?
Naam, kama una n majina katika data hii muundo, Maxwell kuwa moja tu ya
yao, ni nini wakati mbio ya kuingiza au kutafuta Maxwell?
Nini wakati mbio wa kuingiza Maxwell?
Kama kuna n majina mengine tayari katika meza?
Yeah?
>> MWANAFUNZI: [inaudible].
>> SPIKA 1: Yeah, ni urefu ya jina, haki?
Hivyo M--x-w-e-l-l hivyo anahisi kama hii algorithm ni kubwa O ya saba.
Sasa, bila shaka, jina zitatofautiana kwa urefu.
Labda ni jina fupi.
Labda ni jina tena.
Lakini nini muhimu hapa ni kwamba ni idadi ya mara kwa mara.
Na labda ni kweli mara kwa mara, lakini mungu, kama realistically, katika
kamusi, pengine kuna baadhi ya kikomo juu ya idadi ya herufi katika
jina la mtu katika nchi fulani.
>> Na hivyo tunaweza kudhani kuwa thamani ni mara kwa mara.
Mimi sijui ni nini.
Ni pengine kubwa kuliko tunafikiri ni.
Kwa sababu kuna daima kona baadhi kesi na jina mambo ya muda mrefu.
Basi hebu kuiita k, lakini bado mara kwa mara labda, kwa sababu kila
jina duniani, angalau katika nchi fulani, ni kwamba urefu au
mfupi, hivyo ni mara kwa mara.
Lakini wakati tumekuwa alisema kitu ni kubwa O ya thamani ya mara kwa mara, nini kwamba
kweli sawa na?
Hiyo ni kweli kitu kimoja kama akisema wakati mara kwa mara.
>> Sasa sisi ni aina ya cheating, haki?
Sisi ni aina ya leveraging baadhi ya nadharia hapa kusema kisima utaratibu wa k ni
kweli ili tu ya moja, na ni mara kwa mara wakati.
Lakini ni kweli ni.
Kwa sababu ufahamu muhimu hapa ni kwamba kama sisi n majina tayari katika hii
data muundo, na sisi Insert Maxwell, ni kiasi cha muda inachukua sisi
kuingiza Maxwell wakati wote walioathirika na jinsi watu wengine wengi
ni katika muundo wa data?
Haionekani kuwa.
Kama mimi alikuwa bilioni mambo zaidi na hii trie, na kisha kuingiza Maxwell, ni
yeye wakati wote walioathirika?
No
Na kwamba ni tofauti yoyote ya data siku miundo tumeona hivi sasa, ambapo
wakati mbio ya algorithm yako ni kujitegemea kabisa ya kiasi gani
mambo ni au si tayari katika kuwa muundo data.
>> Na hivyo na hii erbjuder wewe sasa ni fursa kwa p seti sita, ambayo itakuwa
tena kuhusisha kutekeleza yako mwenyewe Spell kusahihisha, kusoma katika 150,000
maneno, namna bora ya kuhifadhi kwamba ni lazima si dhahiri.
Na ingawa nimekuwa aspired kupata grail takatifu, sijui
kudai kwamba trie ni.
Kwa kweli, meza hash anaweza vizuri sana kuthibitisha kuwa ufanisi mkubwa zaidi.
Lakini wale ni tu -
hiyo ni moja tu ya maamuzi ya kubuni utakuwa na kufanya.
>> Lakini katika kufunga hebu kuchukua 50 au hivyo sekunde kuchukua Peek katika kile uongo
mbele wiki ijayo na zaidi ya mpito sisi kutoka hii mstari amri
dunia kama C mipango ya mtandao mambo msingi na na lugha kama PHP
JavaScript na biashara yenyewe, itifaki kama HTTP, ambayo wewe wameweza
kuchukuliwa kwa nafasi kwa miaka sasa, na typed wengi kila
siku, labda, au kuonekana.
Na tutaweza kuanza peel nyuma tabaka ya nini ni ya internet.
Na ni nini kificho kwamba underlies leo zana.
Hivyo 50 sekunde ya teaser hii hapa.
Nawapa Warriors ya Net.
>> [Video avspelning]
>> -Yeye alikuja na ujumbe.
Na itifaki ya yote peke yake.
Yeye alikuja kwa dunia ya mpenyo kikatili, asiyejali ruta, na hatari ya mbali
mbaya zaidi kuliko kifo.
Yeye ni kufunga.
Yeye ni nguvu.
Yeye ni TCPIP.
Na yeye got anwani yako.
Warriors ya Net.
>> [MWISHO video avspelning]
>> SPIKA 1: Hiyo ni jinsi ya internet atakuwa kazi kama ya wiki ijayo.