SPIKA 1: Haki wote, hivyo hii ni CS50 Hii ni mwisho wa wiki tano. Na kukumbuka wakati huo jana sisi kuanza kuangalia data fancier miundo ambayo ilianza kutatua matatizo, ambayo ilianza kuanzisha matatizo mapya, lakini muhimu kwa hii ilikuwa ni aina ya threading kwamba sisi kuanza kufanya kutoka nodi ili nodi. Hivyo hii bila shaka ni orodha moja moja wanaohusishwa. Na kwa moja moja wanaohusishwa, I mean kuna moja tu thread kati ya kila moja ya nodes hizo. Zamu nje unaweza kufanya fancier mambo kama orodha doubly wanaohusishwa ambapo una mshale kwenda katika pande zote mbili, ambayo inaweza kusaidia na ufanisi fulani. Lakini hii kutatuliwa tatizo? Tatizo gani hii kutatua? Kwa nini sisi huduma siku ya Jumatatu? Kwa nini, katika nadharia, je sisi huduma siku ya Jumatatu? Je, ni nini? 

Watazamaji: Tunaweza dynamically resize yake. 

SPIKA 1: OK, hivyo tunaweza dynamically resize yake. Vizuri nyote wawili. Hivyo unaweza dynamically resize hii muundo wa data, ambapo safu, wanakumbuka, una kujua priori kiasi gani nafasi unataka na kama unahitaji zaidi kidogo nafasi, wewe ni aina ya nje ya bahati. Una kujenga nzima mwezi safu. Una hoja zote za yako data kutoka moja hadi nyingine, Hatimaye bure safu miaka kama unaweza, na kisha kuendelea. Ambayo tu anahisi gharama kubwa sana na sana ufanisi, na kwa kweli inaweza kuwa. Lakini hii si yote mazuri. Sisi kulipa bei, nini ilikuwa moja ya bei ya wazi zaidi sisi kulipa kwa kutumia orodha wanaohusishwa? 

Watazamaji: Tuna kutumia mara mbili nafasi kwa kila mmoja. SPIKA 1: Yeah, hivyo tunahitaji angalau mara mbili kama nafasi sana. Kwa kweli, mimi barabara hii picha ya hata kidogo kupotosha, kwa sababu ya CS50 IDE katika mengi ya kisasa kompyuta, pointer au anwani si kwa kweli ka nne. Ni mara nyingi sana hawa Siku ka nane, ambayo ina maana chini zaidi mistatili huko katika hali halisi ni aina ya mara mbili kama kubwa kama nini nimekuwa inayotolewa, ambayo ina maana unatumia mara tatu kama nafasi sana kama tuwe na vinginevyo. Sasa wakati huo huo, sisi ni bado anasema ka, sawa? Sisi siyo lazima kuzungumza megabytes au gigabytes, isipokuwa takwimu hizi miundo kupata kubwa. 

Na hivyo leo sisi kuanza kufikiria jinsi tupate kuchunguza data ufanisi zaidi ikiwa katika ukweli data anapata kubwa. Lakini hebu jaribu canonicalize shughuli kwanza ambayo unaweza kufanya juu ya haya aina ya miundo data. Hivyo kitu kama wanaohusishwa orodha ujumla inasaidia shughuli kama kufuta, kuingiza, na kutafuta. Na je, mimi maana na kwamba? Hiyo ina maana kwamba kwa kawaida tu, kama watu wanatumia orodha wanaohusishwa, wao au mtu mwingine imetekeleza kazi kama kufuta, kuingiza, na utafutaji, hivyo unaweza kweli kufanya kitu muhimu na muundo data. Basi hebu tuangalie kwa haraka jinsi tupate kutekeleza baadhi kificho kwa orodha wanaohusishwa kama ifuatavyo. 

Hivyo hii ni baadhi tu ya C kificho, hata mpango kamili kwamba mimi kwa kweli kwa haraka kuchapwa up. Siyo online katika usambazaji kanuni, kwa sababu itakuwa si kweli kuendesha. Lakini taarifa Nimekuwa tu kwa maoni alisema, dot dot dot, kuna kitu huko, dot dot dot, kitu huko. Na hebu tu kuangalia sehemu gani Juicy ni. Hivyo kwenye mstari tatu, kukumbuka kwamba hii ni sasa sisi mapendekezo kutangaza nodi mwisho muda, moja ya vitu wale mstatili. Ina int kwamba tutaweza wito N, lakini tunaweza kuiita kitu chochote, na kisha nyota struct nodi aitwaye ijayo. Na tu kuwa wazi, kwamba pili mstari, juu ya mstari sita, ni nini hiyo? Je, ni kwa kufanya kwa ajili yetu? Kwa sababu ni hakika inaonekana zaidi cryptic kuliko vigezo yetu ya kawaida. 

Watazamaji: Ni inafanya hoja juu moja. 

SPIKA 1: Ni inafanya hoja juu moja. Na kuwa sahihi zaidi, itakuwa kuhifadhi anuani ya nodi kwamba maana ya kuwa semantically karibu na hiyo, sawa? Hivyo si kwenda lazima hoja ya kitu chochote. Ni kwenda tu kwa kuhifadhi thamani, ambayo ni kwenda kuwa anuani baadhi nodi mengine, na hii ndiyo sababu tumekuwa alisema struct nyota nodi, nyota denoting pointer au mahali. OK, hivyo sasa kama wewe kudhani kwamba tuna N huu kwa ajili yetu, na hebu kudhani kuwa mtu mwingine ina kuingizwa rundo zima la integers ndani ya orodha wanaohusishwa. Na orodha hiyo wanaohusishwa ni alisema kwa baadhi ya uhakika kutofautiana kuitwa orodha hiyo ni kupita katika hapa kama parameter, jinsi gani mimi kwenda kuhusu mstari 14 kutekeleza search? Kwa maneno mengine, ikiwa ni utekelezaji wa mimi kazi ambao lengo katika maisha ni kuchukua int na kisha mwanzo wa orodha wanaohusishwa, kuwa ni pointer orodha wanaohusishwa. Kama kwanza, ambaye nadhani Daudi Ilikuwa kujitolea yetu juu ya Jumatatu, alikuwa akionyesha zima wanaohusishwa orodha, ni kana kwamba sisi ni kupita David katika kama hoja yetu hapa. Je, sisi kwenda juu apitaye orodha hii? Naam, zinageuka kuwa hata kama kuyatumia ni kipya sasa kwa sisi, tunaweza kufanya hivyo kiasi straightforwardly. 

Mimi nina kwenda kwenda mbele na kutangaza kutofautiana muda kwamba kwa mkataba ni kwenda tu kuitwa pointer, au PTR, lakini unaweza kuiita kitu chochote unataka. Na mimi nina kwenda initialize kwa mwanzo wa orodha. Hivyo unaweza aina ya kufikiria hii kama mimi mwalimu siku nyingine, aina ya akionyesha mtu miongoni mwa binadamu wetu kama kujitolea. Kwa hiyo mimi nina variable muda hiyo ni tu akionyesha kitu kimoja kwamba yetu kwa bahati aitwaye kujitolea David pia alikuwa anaonyesha. Sasa wakati pointer ni si null, kwa sababu wanakumbuka kwamba null ni baadhi ya thamani maalum mwangalizi demarcates mwisho wa orodha, hivyo wakati mimi si akionyesha ardhi kama kujitolea yetu ya mwisho Ilikuwa, hebu kwenda mbele na kufanya yafuatayo. Kama pointer na sasa mimi aina ya kutaka kufanya kile sisi alivyofanya kwa mwanafunzi structure-- kama pointer dot ijayo equals-- badala yake, ikiwa pointer dot N sawa na sawa kutofautiana N, Hoja hiyo imekuwa kupita katika, kisha nataka kwenda mbele na kusema kurudi kweli. Nimeona idadi N ndani ya moja ya nodes ya orodha yangu wanaohusishwa. Lakini nukta tena kazi katika mazingira haya, kwa sababu pointer, PTR, ni Hakika pointer, mitaani, sisi kweli unaweza ajabu kutumia hatimaye kipande cha syntax aina hiyo ya hufanya Intuitive hisia na kwa kweli kutumia mshale hapa, ambayo ina maana kwenda kutoka kwamba hotuba yake kwa integer huko katika. Hivyo ni sawa sana katika roho kwa nukta operator, lakini kwa sababu pointer ni si pointer na si struct halisi yenyewe, sisi tu kutumia mshale. 

Hivyo kama nodi sasa kwamba mimi, kutofautiana kwa muda, ni akionyesha si N, je, nataka kufanya? Naam, kwa kujitolea yangu binadamu kwamba tulikuwa hapa siku nyingine, kama binadamu yangu ya kwanza siyo mimi moja wanataka, na labda binadamu pili ni si moja nataka, na wa tatu, mimi haja ya kuendelea kusonga kimwili. Kama jinsi gani mimi hatua kupitia orodha? Wakati tulikuwa safu, wewe tu alifanya kama mimi pamoja na plus. Lakini katika kesi hii, yatosha kufanya pointer, anapata, pointer, ijayo. Kwa maneno mengine, shamba ujao Ni kama yote ya mikono kushoto kwamba kujitolea yetu ya kibinadamu Jumatatu walikuwa kutumia kwa uhakika katika baadhi nodi wengine. Wale walikuwa majirani zao ijayo. 

Hivyo kama nataka hatua kupitia orodha hii, Siwezi tu kufanya mimi pamoja pamoja tena, Mimi badala kusema Mimi, pointer, ni kwenda kwa sawa chochote shamba pili ni, shamba pili ni, shamba pili ni, kufuatia zote za mikono wale kushoto kwamba tulikuwa juu ya hatua akizungumzia na maadili ya baadhi ya baadae. Na kama mimi kupata njia kuwa iteration nzima, na hatimaye, mimi kugonga null kutokuwa na kupatikana N bado, mimi tu kurudi uongo. Hivyo tena, kila kitu sisi ni kufanya hapa, kwa mujibu wa picha wakati iliyopita, ni mapya na akionyesha mwanzo wa orodha labda. Na kisha mimi kuangalia, ni thamani Mimi nina kuangalia kwa sawa na tisa? Kama ni hivyo, mimi kurudi kweli na mimi nina kufanyika. Kama siyo, mimi update mkono wangu, AKA pointer, kwa uhakika katika mshale ujao eneo, na kisha mshale ujao eneo, na ijayo. Mimi tu kutembea kwa njia ya safu hii. 

Hivyo tena, anayejali? Kama ni kitu gani kingo kwa? Naam, kukumbuka kuwa sisi ilianzisha dhana ya stack, ambayo ni data abstract aina kadiri ni si C kitu, siyo CS50 kitu, ni wazo dhahania, wazo hili la stacking vitu juu ya mtu mwingine ambayo yanaweza kutekelezwa katika mashada ya njia tofauti. Na njia moja sisi mapendekezo alikuwa pamoja safu, au kwa orodha wanaohusishwa. Na zinageuka kuwa canonically, stack inasaidia shughuli angalau mbili. Na maneno buzz ni kushinikiza, kwa kushinikiza kitu kwenye stack, kama tray mpya katika jumba la kulia chakula, au pop, ambayo ina maana ya kuondoa topmost tray kutoka mkusanyiko katika dining ukumbi, na kisha labda baadhi shughuli nyingine pia. Hivyo ni jinsi gani sisi kufafanua muundo kwamba sisi ni sasa wito stack? 

Naam, tuna zote za zinazohitajika syntax tulizonazo katika C. nasema, nipe aina ufafanuzi wa struct ndani ya stack, Mimi nina kwenda kusema ni safu, wa rundo zima la idadi na kisha ukubwa. Hivyo kwa maneno mengine, kama nataka kutekeleza hili katika kanuni, basi mimi kwenda na aina tu ya kuteka nini hii ni kusema. Hivyo hii ni kusema, nipe muundo kwamba got safu, na sijui uwezo ni nini, ni inaonekana baadhi ya mara kwa mara kwamba nimekuwa inavyoelezwa mahali pengine, na hiyo ni nzuri. Lakini tuseme ni tu moja, mbili, tatu, nne, tano. Hivyo uwezo ni 5. Hili kipengele ndani ya yangu muundo wa wataitwa namba. Na kisha mimi haja moja kutofautiana wengine inaonekana aitwaye ukubwa ambayo awali mimi nina kwenda kwa inasema ni initialized kwa sifuri. Kama kuna kitu katika stack, ukubwa ni sifuri, na ni takataka maadili kwa idadi. Mimi sijui nini huko bado tu. 

Hivyo kama nataka kushinikiza kitu kwenye stack, nadhani piga kazi kushinikiza, na Nasema kushinikiza 50, kama idadi 50, ambapo ingekuwa wewe kupendekeza Mimi kuteka ni katika safu hii? Kuna baadhi ya majibu tano tofauti iwezekanavyo. Wapi unataka kushinikiza idadi 50? Kama lengo hapa, tena, piga kazi kushinikiza, kupita katika hoja ya 50, ambapo mimi kuiweka? Tano possible-- 20% chance ya kubahatisha kwa usahihi. Ndiyo? 

Watazamaji: Mbali haki. 

SPIKA 1: Mbali haki. Kwa sasa kuna 25% chance ya kubahatisha kwa usahihi. Hivyo kwamba ingekuwa kweli kuwa faini. Kwa mkataba huo, mimi itabidi kusema kwa safu, tunataka ujumla kuanza saa kushoto, lakini tunaweza hakika kuanza upande wa kulia. Hivyo spoiler hapa itakuwa mimi nina pengine ni kwenda kuteka ni upande wa kushoto, tu kama katika safu ya kawaida ambapo Mimi kuanza kwenda kushoto na haki. Lakini kama unaweza flip hesabu, faini. Ni tu si ya kawaida. OK, mimi haja ya kufanya moja Mabadiliko zaidi ingawa. Sasa kwa kuwa nimekuwa kusukuma kitu kwenye stack, nini hapo? 

Haki wote, mimi na increment kawaida. Hivyo basi mimi kwenda mbele na tu update hii, ambayo ilikuwa sifuri. Na badala yake sasa, mimi nina kwenda kuweka katika thamani moja. Na sasa nadhani kushinikiza mwingine idadi kwenye stack, kama 51. Naam, nina kufanya moja zaidi mabadiliko, ambayo ni juu ya ukubwa mbili. Na kisha nadhani kushinikiza moja zaidi idadi kwenye stack kama 61, sasa mimi haja ya update ukubwa moja zaidi muda, na kupata thamani kama 3 ukubwa. Na sasa nadhani kuwaita pop. Sasa pop, na mkataba huo, haina kuchukua hoja. Kwa stack, wote hatua ya tray mfano ni kwamba huna busara kwenda kupata kwamba tray, wote unaweza kufanya ni pop topmost mmoja kutoka stack, kwa sababu tu. Hiyo ni nini muundo huu data gani. 

Hivyo kwa mantiki kwamba kama mimi kusema pop, nini huja mbali? Hivyo 61. Hivyo kile kwa kweli ni kompyuta kwenda kufanya katika kumbukumbu? Je kificho wangu una kufanya? Je utafanya kupendekeza sisi kubadili juu ya screen? Nini wanapaswa kubadilika? Pole? Hivyo sisi kujikwamua 61. Hivyo siwezi dhahiri kufanya hivyo. Na siwezi kujikwamua 61. Na kisha nini wengine mabadiliko mahitaji ya kutokea? Ukubwa pengine ina kurudi miwili. Na hivyo hiyo ni nzuri. Lakini kusubiri dakika, ukubwa wakati iliyopita alikuwa tatu. Hebu tu kufanya haraka sanity hundi. Jinsi gani tunajua kwamba sisi alitaka kujikwamua 61? Kwa sababu sisi ni yanajitokeza. Na hivyo nina hii ya pili ya mali ukubwa. 

Hebu subiri kidogo, mimi nina kufikiri nyuma wiki mbili wakati sisi kuanza kuzungumza juu ya arrays, ambapo hii ilikuwa eneo sifuri, hii ilikuwa eneo moja, hii ilikuwa ni eneo mbili, hii ni eneo tatu, nne, inaonekana kama Uhusiano kati ya ukubwa na kipengele kwamba mimi nataka kuondoa kutoka safu inaonekana kuwa kile tu? Ukubwa bala moja. Na hivyo hiyo ni jinsi kama binadamu tunajua 61 anakuja kwanza. Jinsi ni kompyuta kwenda kujua? Wakati kanuni yako, ambapo pengine wanataka kufanya ukubwa bala moja, hivyo tatu bala moja ni mbili, na kwamba ina maana tunataka kujikwamua 61. Na kisha tunaweza kweli kuboresha ukubwa ili ukubwa sasa huenda 3-2 tu. Na tu kuwa pedantic, mimi nina kwenda kupendekeza kwamba mimi nina kufanyika, sawa? Wewe mapendekezo shirikishi usahihi ni lazima kujikwamua 61. Bali awe na si mimi aina ya aina ya kujipatia kuondoa 61? Nimekuwa kwa ufanisi wamesahau kwamba ni kweli kuna. Na kufikiri nyuma pset4, kama wameweza kusoma makala kuhusu forensics, PDF kwamba tulikuwa na nyie kusoma, au wewe kusoma wiki hii kwa pset4. Kumbuka kwamba hii ni kweli germane na Wazo zima la forensics kompyuta. Nini kompyuta kwa ujumla haina ni tu kusahau ambapo kitu ni, lakini haina kwenda katika na kama kujaribu scratch nje au override bits wale wenye zeros na ndio au nyingine random mfano isipokuwa wewe mwenyewe kufanya hivyo kwa makusudi. Hivyo Intuition yako alikuwa haki, hebu kujikwamua 61. Lakini katika hali halisi, hatuna kujisumbua. Sisi tu haja ya kusahau kwamba ni huko kwa kubadilisha ukubwa yetu. 

Sasa kuna tatizo na mkusanyiko huu. Kama mimi kuweka kusukuma mambo kwenye stack, nini wazi kinaenda kutokea katika dakika chache tu wakati? Tunakwenda kukimbia nje ya nafasi. Na tunafanya nini? Sisi ni aina ya Star. Utekelezaji huu hana basi sisi resize safu, kwa sababu kwa kutumia syntax hii, kama wewe kufikiri nyuma kwa wiki mbili, mara moja umefanya alitangaza ukubwa wa safu, hatujaona utaratibu bado ambapo unaweza kubadilisha ukubwa wa safu. Na hakika C haina kipengele hicho. Kama umesema nipe tano Nths, kuwaita idadi, hayo ni yote wewe ni kwenda kupata. Kwa hiyo sisi kufanya sasa kama ya Jumatatu, na uwezo wa kueleza ufumbuzi ingawa, sisi tu haja ya tweak ufafanuzi wa stack yetu kwa kuwa baadhi ya safu ngumu-coded, lakini tu kuhifadhi mahali. 

Sasa kwa nini hii? Sasa sisi tu kuwa starehe na ukweli kwamba wakati mpango wangu anaendesha, Mimi labda kwenda na kuuliza binadamu, jinsi wengi idadi gani unataka kuhifadhi? Hivyo pembejeo ana kuja kutoka mahali fulani. Lakini mara Najua kwamba idadi, basi naweza tu kutumia nini kazi kutoa mimi chunk ya kumbukumbu? Naweza kutumia malloc. Na naweza kusema idadi yoyote ya ka Nataka nyuma kwa Nths haya. Na mimi wote wana kuhifadhi kwa idadi kutofautiana hapa ndani ya struct hii lazima nini? Ni nini hasa yanayoendelea ndani idadi katika tukio hili? Naam, pointer kwanza Byte ya kwamba chunk ya kumbukumbu, au zaidi hasa, anwani ya kwanza ya ka hizo. Haijalishi kama ni moja Byte au bilioni ka, Mimi tu haja ya huduma kuhusu kwanza. Kwa sababu gani dhamana malloc na mfumo wa uendeshaji yangu dhamana, ni kwamba chunk ya kumbukumbu mimi kupata, ni kwenda kuwa contiguous. Kuna si kwenda kuwa na mapungufu. Hivyo kama nimekuwa aliuliza kwa 50 ka ka au 1,000, wao ni wote kwenda kuwa nyuma kwa nyuma kwa nyuma. Na hivyo muda mrefu kama mimi kukumbuka jinsi kubwa, jinsi gani mimi kuomba, kila nahitaji kujua ni kwanza anuani hizo. 

Hivyo basi, tuna uwezo katika kanuni. Angalau, ni kwenda kuchukua yetu muda zaidi wa kuandika hii up, tunaweza sasa reallocate kwamba kumbukumbu na tu kuhifadhi anwani tofauti huko kama tunataka kubwa au hata chunk ndogo ya kumbukumbu. Hivyo hapa kwa biashara mbali. Sasa sisi kupata mabadiliko. Bado tuna contiguousness mimi nina wakidai. Kwa sababu malloc itatupa chunk contiguous ya kumbukumbu. Lakini hii ni kwenda kuwa maumivu katika shingo kwa ajili yetu, programu, kwa kweli kanuni up. Ni kazi tu zaidi. Tunahitaji kificho sawa na kile Mimi nilikuwa banging nje muda tu iliyopita. Doable sana, lakini inaongeza utata. Na hivyo developer huo, programu wakati bado rasilimali nyingine ili tupate haja ya kutumia muda kupata makala mpya. Na kisha bila shaka kuna foleni. Sisi si kwenda katika hii moja kwa undani zaidi. Lakini ni sawa sana katika ulimwengu wa kiroho. Mimi naweza kutekeleza foleni, na shughuli zake inayolingana, enqueue au dequeue, kama kuongeza au kuondoa, ni njia tu fancier ya kusema hayo, enqueue au dequeue, kama ifuatavyo. Naweza tu kutoa mwenyewe struct kuwa tena ina safu idadi ya, kuwa tena ina ukubwa, lakini kwa nini mimi sasa haja kuweka wimbo wa mbele ya foleni? Mimi hakuwa na haja ya kujua mbele ya mkusanyiko yangu. Naam, kama mimi tena kwa queue-- hebu bidii tu kanuni ni kama kuwa kama tano integers humu uwezekano. Hivyo hii ni sifuri, moja, mbili, tatu, nne. Hii ni kwenda kuwa aitwaye idadi tena. Na hii wataitwa ukubwa. 

Kwa nini ni hautoshi kuwa na ukubwa tu? Naam, hebu kushinikiza wale idadi hiyo juu. Hivyo mimi pushed-- mimi enqueued, au kusukuma. Sasa mimi itabidi enqueue 50, na kisha 51, na kisha 61, na dot dot dot. Hivyo hiyo ni enqueue. Mimi enqueued 50, kisha 51, kisha 61. Na kwamba inaonekana kufanana kwa stack hivi sasa, isipokuwa mimi haja ya kufanya mabadiliko moja. Mimi haja ya kuboresha ukubwa huu, hivyo mimi kwenda kutoka sifuri kwa moja kwa 2-3 sasa. Je, mimi dequeue? Nini kinatokea na dequeue? Nani anapaswa kufika mbali orodha hii ya kwanza ikiwa ni mstari katika Apple Hifadhi? Hivyo 50. Hivyo ni aina ya trickier kipindi hiki. Wakati mara ya mwisho ilikuwa ni super rahisi tu kufanya ukubwa bala moja, Mimi kupata mwisho wa safu yangu kwa ufanisi ambapo idadi ni, ni kuondosha 61. Lakini sitaki kuondoa 61. Nataka kuchukua 50, ambaye Ilikuwa pale katika 05:00 kujipanga kwa iPhone mpya au whatnot. Na hivyo kujikwamua 50, mimi Huwezi tu kufanya hivyo, haki? Siwezi kuvuka nje 50. Lakini sisi tu alisema sisi Si lazima iwe hivyo anal kama scratch nje au kujificha data. Tunaweza kusahau tu ambapo ni. 

Lakini kama mimi mabadiliko ya kawaida yangu sasa kwa mbili, ni habari hii kutosha kujua ni nini kinaendelea katika foleni wangu? Si kweli. Kama kawaida yangu ni mbili, lakini wapi foleni kuanza, hasa kama mimi bado wana wale idadi sawa katika kumbukumbu. 50, 51, 61. Hivyo mimi haja ya kukumbuka sasa ambapo mbele ni. Na hivyo kama mimi mapendekezo juu huko, tutaweza kuwa tu kuitwa Nth mbele, ambaye awali thamani lazima wamekuwa nini? Sifuri, mwanzo tu wa orodha. Lakini sasa pamoja na decrementing ukubwa, sisi tu increment mbele. Sasa hapa kuna tatizo jingine. Hivyo mara mimi kuendelea kwenda. Tuseme hii ndiyo hesabu ya kama 121, 124, na kisha, Dammit, Mimi nina nje ya nafasi. Lakini kusubiri dakika, mimi si. Hivyo katika hatua hii ya hadithi, tuseme kwamba ukubwa ni moja, mbili, tatu, nne, hivyo kudhani kuwa ukubwa ni nne, mbele ni moja, hivyo 51 ni mbele. Nataka kuweka namba nyingine hapa, lakini, Dammit, mimi nina nje ya nafasi. Lakini mimi si kweli, haki? Ambapo nitaweza kuweka baadhi thamani ya ziada, kama 171? Naam, mimi naweza tu aina ya kurudi nyuma zaidi ya hapo, sawa? Na kisha kuvuka nje 50, au tu overwrite ni pamoja na 171. Na kama wewe wanashangaa kwa nini idadi yetu got hivyo bila mpangilio, hizi ni kawaida kuchukuliwa kompyuta kozi ya sayansi katika Harvard baada CS50. Lakini hiyo ilikuwa optimization nzuri, kwa sababu sasa mimi si kupoteza nafasi. Bado nina kukumbuka jinsi kubwa jambo hili ni jumla. Ni jumla mitano. Kwa sababu mimi sitaki kuanza overwriting 51. Hivyo sasa mimi bado nje ya nafasi, hivyo tatizo sawa mbele. Lakini unaweza kuona jinsi sasa katika kanuni yako, pengine kuandika kidogo zaidi utata kwa kufanya kutokea. Na kwa kweli, operator nini katika C pengine lets wewe magically kufanya hivyo circularity? Yeah modulo operator, asilimia ishara. Kwa hiyo kile ni aina ya baridi kuhusu foleni, ingawa sisi kuendelea kuchora arrays kama hizi mistari kama moja kwa moja, kama wewe aina ya kufikiri juu ya hili kama curving karibu kama mduara, basi tu shirikishi ni aina ya kazi kiakili Nadhani kidogo zaidi cleanly. Ungependa bado kuwa na kutekeleza kuwa mfano wa akili katika kanuni. Hivyo si kwamba ni vigumu, hatimaye, kutekeleza, lakini bado tunapoteza size-- badala yake, uwezo wa resize, isipokuwa sisi kufanya hivyo. 

Tuna kujikwamua safu, sisi badala yake pamoja na pointer moja, na kisha mahali fulani katika kanuni yangu mimi nimepata a kuwaita nini kazi kwa kweli kujenga safu kuitwa namba? Malloc, au baadhi sawa kazi, hasa. Maswali yoyote juu ya mwingi au foleni. Yeah? Nzuri swali. Nini modulo gani unaweza kutumia hapa. Hivyo kwa ujumla, wakati wa kutumia Mod, ungekuwa kufanya hivyo na ukubwa wa data zima muundo. Hivyo kitu kama tano au uwezo, ikiwa ni mara kwa mara, pengine ni kushiriki. Lakini tu kufanya modulo tano pengine si ya kutosha, kwa sababu tunahitaji kujua nini sisi kufungia hapa au hapa au hapa. Hivyo wewe pengine pia atataka kuhusisha ukubwa wa jambo, au kutofautiana mbele pia. Hivyo ni tu hii kiasi rahisi hesabu kujieleza, lakini modulo itakuwa kiungo muhimu. 

Hivyo filamu fupi kama wewe. Uhuishaji kwamba baadhi folks katika chuo kikuu mwingine kuweka pamoja kwamba tumekuwa ilichukuliwa kwa mjadala huu. Inahusisha Jack kujifunza ukweli kuhusu foleni na takwimu. 

FILM: Mara juu ya muda, kulikuwa na guy aitwaye Jack. Linapokuja suala la kufanya marafiki, Jack hakuwa na knack. Hivyo Jack alikwenda kuzungumza na maarufu guy alijua. Alikwenda Lou na kuuliza, Je, nini? Lou alipoona kwamba rafiki yake alikuwa kweli kuhangaika. Naam, alianza, tu kuangalia jinsi wewe ni amevaa. Je, si una nguo yoyote kwa kuangalia tofauti? Ndiyo, alisema Jack. Mimi uhakika kufanya. Kuja nyumbani kwangu na Mimi itabidi kuonyesha hao na wewe. Basi, wakaenda mbali na Jack ya. Na Jack ilionyesha Lou sanduku ambapo aliendelea mashati wake wote, na suruali yake, na soksi yake. Lou alisema, Mimi naona una nguo yako yote katika fungu. Mbona wewe kuvaa baadhi wengine mara moja katika muda? 

Jack alisema, vizuri, wakati mimi vua nguo na soksi, Mimi safisha yao na kuweka yao mbali katika eneo la hatari. Kisha huja ijayo asubuhi, na hadi mimi hop. Mimi kwenda sanduku na kupata nguo zangu mbali juu. Lou haraka waligundua Tatizo la Jack. Aliendelea nguo, CD, na vitabu katika stack. Alipofika kwa kitu cha kusoma au kuvaa, yeye d kuchagua kitabu juu au chupi. Na alipo ilifanyika, yeye bila kuweka ni haki ya nyuma. Nyuma ingekuwa kwenda, juu ya stack. Najua ufumbuzi, Alisema ushindi Loud. Unahitaji kujifunza kwa kuanza kutumia foleni. Lou alichukua nguo Jack na Hung yao kwa kujificha. Alipomaliza kumwagwa sanduku, yeye tu kuchafuka. 

Akasema, sasa Jack, mwishoni mwa siku, kuweka nguo yako upande wa kushoto wakati kuweka yao mbali. Kisha kesho asubuhi wakati ona jua, kupata nguo yako juu ya haki, kutoka mwisho wa mstari. Je, unaweza kuona? Alisema Lou. Itakuwa hivyo nice. Itabidi kuvaa kila kitu mara moja kabla kuvaa kitu mara mbili. Na kwa kila kitu katika foleni katika chumbani kwake na rafu, Jack kuanza kujisikia uhakika kabisa ya nafsi yake. Mafanikio hayo yanatokana na Lou na foleni yake ya ajabu. SPIKA 1: Haki wote, ni adorable. Kwa hiyo kile imekuwa kweli kwenda chini ya Hood sasa? Kwamba tuna kuyatumia, kwamba tuna malloc, kwamba tuna uwezo wa kujenga bonge la kumbukumbu kwa wenyewe dynamically. Hivyo hii ni picha sisi glimpsed tu siku nyingine. Sisi si kweli kukaa juu ya jambo hilo, lakini picha hii ina wamekuwa kinachoendelea chini kofia kwa muda wa wiki sasa. Na hivyo hii inawakilisha, tu Mstatili kwamba tumekuwa inayotolewa, kumbukumbu ya kompyuta yako. Na labda kompyuta yako, au CS50 Kitambulisho, ina gigabyte ya kumbukumbu au RAM au gigabytes mbili au nne. Ni kweli haina jambo. Mfumo wa uendeshaji wako Windows au Mac OS au Linux, kimsingi inaruhusu programu yako kufikiri kwamba ina upatikanaji kwa ukamilifu wa kumbukumbu ya kompyuta yako, hata ingawa unaweza kuwa mbio programu mbalimbali kwa wakati mmoja. Hivyo katika hali halisi, kwamba si kweli kazi. Lakini ni aina ya udanganyifu aliyopewa wote wa programu yako. Hivyo kama wewe alikuwa gigs mbili ya RAM, hii ni jinsi ya kompyuta inaweza kufikiria ni. 

Sasa kwa bahati, mmoja wa haya mambo, moja ya makundi haya ya kumbukumbu, inaitwa stack. Na hakika wakati wowote hivi sasa kwa maandishi kificho kwamba wametoa wito kazi, kwa mfano kuu. Kumbuka kwamba wakati wowote nimekuwa kumbukumbu inayotolewa kompyuta, Mimi daima kuteka aina ya nusu ya Mstatili hapa na wala bother kuzungumza kuhusu nini hapo juu. Kwa sababu wakati kuu inaitwa, mimi kudai kwamba kupata ikilinganishwa na kiasi hiki cha kumbukumbu kwamba huenda chini hapa. Na kama kuu wito kazi kama wabadilishane, vizuri wabadilishane huenda hapa. Na zinageuka, hiyo ni ambapo ni kuishia. On kitu kinachoitwa stack ndani ya kumbukumbu ya kompyuta yako. Sasa mwisho wa siku, hii ni anazungumzia tu. Ni kama Byte sifuri, Byte moja, Byte bilioni 2. Lakini kama wewe kufikiri juu yake kama hii kitu mstatili, wote sisi ni kufanya kila wakati sisi kuwaita kazi ni layering kipande mpya wa kumbukumbu. Sisi ni kutoa kazi ambayo kipande ya kumbukumbu yake mwenyewe kufanya kazi pamoja. 

Na kukumbuka sasa kwamba hii ni muhimu. Kwa sababu kama hatuwezi kuwa na kitu kama wabadilishane vigezo na mbili ndani kama A na B na sisi kubadili maadili hayo kutoka moja na mbili kwa mbili na moja, kukumbuka kwamba wakati wabadilishane anarudi, ni kana kwamba kipande hii ya kumbukumbu ni gone tu. Katika hali halisi, bado kuna forensically. Na kitu kweli bado kuna. Lakini conceptually, ni kama ingawa ni kabisa gone. Na hivyo kuu hajui chochote cha kazi kwamba ilifanyika katika kwamba wabadilishane kazi, isipokuwa ni kweli kupita katika wale hoja na pointer au ukihusishwa. Sasa, ufumbuzi wa kimsingi kwa kuwa tatizo na wabadilishane anapita mambo katika na mahali. Lakini zinageuka, pia, nini kinachoendelea juu sehemu ambayo ya Mstatili muda wote huu ni lakini kuna zaidi ya kumbukumbu hadi pale. Na wakati dynamically kutenga kumbukumbu, kama ni ndani ya GetString, ambayo tumekuwa kufanya kwa ajili yenu katika CS50 maktaba, au kama nyie piga malloc na kuuliza mfumo wa uendeshaji kwa chunk ya kumbukumbu, haina kuja kutoka stack. Inatoka mahali pengine katika kumbukumbu ya kompyuta yako kwamba wito lundo. Na si kwamba yoyote tofauti. Ni RAM huo. Ni kumbukumbu huo. Ni tu RAM hiyo ni juu huko badala ya chini hapa. 

Na hivyo nini maana gani? Naam, kama kompyuta yako ina kiasi kidogo cha kumbukumbu na stack ni kupanda juu, hivyo kusema, na lundo, kwa mujibu kwa mshale hiyo, ni kuongezeka chini. Kwa maneno mengine, kila wakati wewe piga malloc, wewe ni kupewa kipande ya kumbukumbu kutoka juu, basi labda mdogo punde, basi kidogo chini, kila wakati wewe piga malloc, lundo, ni matumizi, ni aina ya kupanda, kuongezeka karibu na karibu na nini? Stack. Hivyo, jambo hili kuonekana kama wazo nzuri? I mean, ambapo si kweli wazi kile kingine unaweza kufanya kama wewe tu na kiasi kidogo cha kumbukumbu. Lakini hii ni hakika mbaya. Wale mishale miwili ni juu ya ajali shaka kwa mtu mwingine. 

Na zinageuka kuwa mtu mbaya, folks ambao ni nzuri hasa kwa programu, na kujaribu hack katika kompyuta, Unaweza kutumia ukweli huu. Kwa kweli, hebu fikiria kidogo snippet. Hivyo hii ni mfano unaweza kusoma kuhusu kwa undani zaidi juu ya Wikipedia. Tutaweza uhakika wewe katika Makala kama wadadisi. Lakini kuna mashambulizi kwa ujumla inayojulikana kama buffer kufurika kwamba ina kuwepo kwa muda mrefu kama binadamu wamekuwa na uwezo wa kuendesha kumbukumbu ya kompyuta, hasa katika C. Hivyo hii ni mpango holela sana, lakini hebu kusoma kutoka chini kwenda juu. Kuu katika argc char nyota argv. Hivyo ni mpango kwamba inachukua hoja mstari amri. Na wote kuu haina inaonekana ni wito kazi, simu yake F kwa unyenyekevu. Na hupita katika nini? Argv ya moja. Hivyo hupita katika F chochote neno ni kwamba mtumiaji typed katika haraka baada ya jina mpango wa wakati wote. Sana kama Kaisari, au la Vigenere, ambayo unaweza kukumbuka kufanya na argv. 

Kwa hiyo kile ni F? F inachukua katika kamba kama hoja yake pekee, AKA nyota Char, sawa Jambo, kama kamba. Na ni kuitwa kiholela bar katika mfano huu. Na kisha char c 12, tu katika suala layman, kile ni char c mabano 12 kufanya kwa ajili yetu? Nini ni nini? Kugawa kumbukumbu, hasa Ka 12 kwa chars 12. Hasa. Na kisha mstari wa mwisho, koroga na nakala, ve pengine hawajaona. Hii ni kamba nakala kazi ambao lengo katika maisha ni nakala hoja yake ya pili ndani ya hoja yake ya kwanza, lakini tu hadi baadhi idadi ya ka. Hivyo Hoja ya tatu anasema, jinsi wengi ka unapaswa nakala? Urefu wa bar, chochote mtumiaji typed katika. Na yaliyomo ya bar, kamba hiyo, ni kunakiliwa katika kumbukumbu alisema katika utafutaji C. 

Hivyo hii inaonekana aina ya kijinga, na ni. Ni mfano contrived, lakini ni mwakilishi wa darasa la mashambulizi wadudu, njia ya kushambulia mpango. Wote ni mzuri na nzuri kama mtumiaji aina katika neno hilo ni wahusika 11 au wachache, pamoja na backslash sifuri. Nini kama mtumiaji aina katika zaidi ya 11 au 12 au 20 au 50 wahusika? Nini mpango huu kwenda kufanya? Uwezekano seg kosa. Ni kwenda kwa upofu nakala kila kitu katika bar ya juu kwa urefu wake, ambayo ni literally kila kitu katika bar, ndani ya anuani alisema katika C. Lakini C ina tu preemptively kutolewa kama ka 12. Lakini hakuna kuangalia zaidi. Hakuna ikiwa masharti. Hakuna kosa kuangalia hapa. 

Na hivyo kile mpango huu ni kwenda kufanya ni tu upofu nakala jambo moja hadi nyingine. Na hivyo kama sisi kuteka hii kama picha, hapa ni tu ikilinganishwa na kiasi cha nafasi ya kumbukumbu. Hivyo taarifa chini, sisi na mitaa kutofautiana bar. Hivyo kwamba pointer ambayo inaenda store-- badala ya kuwa hoja za mitaa hiyo ni kwenda kuhifadhi kamba bar. Na kisha taarifa tu juu yake katika stack, kwa sababu kila wakati kuuliza kwa kumbukumbu juu ya stack, unaendelea kidogo juu yake pictorially, taarifa kwamba sisi tumepewa ka 12 huko. Juu kushoto moja ni C mabano sifuri na haki ya chini moja ni C mabano 11. Hiyo tu jinsi ya kompyuta kwenda kuweka nje. Hivyo tu intuitively, ikiwa bar ina zaidi kuliko wahusika 12 katika jumla, ikiwa ni pamoja na backslash sifuri, ambapo ni 12 au C mabano 12 kwenda? Au tuseme ambapo ni 12 tabia au tabia ya 13, tabia mia kwenda kuishia katika picha? Juu au chini? 

Haki, kwa sababu hata kama stack yenyewe inakua zaidi, mara moja umefanya kuweka mambo katika hilo, ni kwa sababu za kubuni, unaweka kumbukumbu kutoka juu hadi chini. Hivyo kama nimepata ka zaidi ya 12, wewe ni kwenda kuanza overwrite bar. Sasa hiyo ni mdudu, lakini ni si kweli mpango kubwa. Lakini ni kubwa mpango huo, kwa sababu kuna mambo zaidi kinachoendelea katika kumbukumbu. Hivyo hapa ni jinsi sisi anaweza kuweka hodi, kuwa wazi. Kama mimi niliandika katika hodi katika haraka. H-E-L-L-O backslash sifuri, huishia ndani ya wale ka 12, na tuko super salama. Yote ni sawa. Lakini kama mimi aina ya kitu muda mrefu, uwezekano wa ni kwenda huenda katika bar nafasi. Lakini mbaya lakini, ni zamu nje muda wote huu, ingawa tumekuwa kamwe alizungumzia hivyo, mkusanyiko ni kutumika kwa ajili ya mambo mengine. Siyo tu vigezo mitaa. 

C ni ndogo sana lugha ngazi. Na ni aina ya siri anatumia stack pia kukumbuka wakati kazi ni wito, nini anuani ni wa kazi ya awali, ili iweze kuruka nyuma kazi hiyo. Hivyo wakati wito kuu wabadilishane, miongoni mwa mambo kusukuma kwenye stack si tu swaps vigezo mitaa, au hoja yake, pia kwa siri kusukuma kwenye stack kama kuwakilishwa na kipande nyekundu hapa, ni pepe ya kuu kimwili katika kumbukumbu ya kompyuta yako, hivyo kwamba wakati wabadilishane ni kosa, kompyuta anajua mimi haja ya kwenda nyuma ya kuu na kumaliza utekelezaji kazi kuu. Hivyo hii ni hatari sasa, kwa sababu kama aina ya mtumiaji katika vizuri zaidi ya hodi, kiasi kwamba pembejeo mtumiaji clobbers au overwrites kwamba nyekundu sehemu, kifikra kama kompyuta ya tu kwenda upofu kudhani kuwa ka katika kwamba kipande nyekundu ni anuani ambayo ni lazima kurudi, nini kama adui ni smart kutosha au bahati ya kuweka mlolongo wa ka pale kwamba inaonekana kama ya mitaani, lakini ni pepe ya kificho kwamba yeye au yeye anataka kompyuta kutekeleza badala ya kuu? 

Kwa maneno mengine, kama yale user ni kuandika katika haraka, sio tu kitu kama innocuous hodi, lakini ni kweli kificho hiyo ni sawa kwa kufuta mafaili yote user huyu? Au email password yao kwangu? Au kuanza magogo yao keystrokes, sawa? Kuna njia, hebu inasema leo, waweze aina katika si tu hujambo dunia au majina yao, lakini hawakuweza kimsingi kupita katika kanuni, zeros na ndio, kwamba kompyuta makosa kwa wote kanuni na mahali. Hivyo angalau kwa kiasi fulani abstractly, ikiwa aina ya mtumiaji katika kutosha ushindani kificho kwamba tutaweza kujumlisha hapa kama A. A ni mashambulizi au wanaompinga. Mbaya tu mambo ya ajabu. Sisi hawajali idadi au zeros au ndio leo, kama kwamba wewe kuishia overwriting kwamba sehemu nyekundu, taarifa kwamba mlolongo wa ka. O 835 C sifuri nane sifuri. Na sasa kama makala Wikipedia hapa imependekeza, kama wewe sasa kweli kuanza kuipatia ka katika kompyuta yako kumbukumbu, nini makala Wikipedia ni kupendekeza ni kwamba, nini kama anuani ya kwamba juu kushoto Byte ni 80 C 0 3508. 

Kwa maneno mengine, kama mtu mbaya ni smart kutosha kwa kificho yake kwa kweli kuweka idadi hapa kwamba sambamba na pepe ya kificho yeye au yeye sindano ndani ya kompyuta, wewe Unaweza hila kompyuta kufanya jambo lolote. Kuondoa files, emailing mambo, sniffing trafiki yako, halisi chochote inaweza kuwa hudungwa katika kompyuta. Na hivyo kufurika buffer mashambulizi katika msingi wake ni wajinga tu, mjinga kuu ya safu kwamba hawakuwa na mipaka yake kuchunguzwa. Na hii ni nini ni super hatari na wakati huo huo super nguvu katika C ni kwamba hatuna hakika na upatikanaji wa mahali popote katika kumbukumbu. Ni juu yetu, programmers, wanaoandika kificho awali kuangalia darn urefu wa yoyote arrays kwamba sisi ni kufanyia. Hivyo kuwa wazi, nini kurekebisha? Kama sisi roll nyuma ya hii kanuni, mimi lazima sio tu mabadiliko ya urefu wa bar, nini mwingine anatakiwa kuwa na kuangalia? Nini kingine lazima mimi kuwa kufanya ili kuzuia shambulio hilo kabisa? Sitaki kwa tu upofu kusema kwamba unapaswa nakala ka kama wengi kama ni urefu wa bar. Nataka kusema, nakala kama ka wale wote walio katika bar hadi zilizotengwa kumbukumbu, au 12 maximally. Hivyo mimi wanahitaji aina fulani ya kama hali kwamba hana kuangalia urefu wa bar, lakini kama unazidi 12, sisi kwa bidii tu kificho 12 kama upeo umbali iwezekanavyo. Vinginevyo kinachojulikana buffer kufurika mashambulizi yanaweza kutokea. Chini ya slides hizo, kama wewe ni curious kusoma zaidi ni halisi ya awali makala kama Ningependa kuchukua kuangalia. 

Lakini sasa, miongoni mwa bei kulipwa hapa ilikuwa kukosekana kwa ufanisi. Hivyo kwamba alikuwa na haraka kiwango cha chini kuangalia nini matatizo yanaweza kutokea sasa kwamba sisi wanapata kumbukumbu ya kompyuta. Lakini tatizo jingine sisi tayari mashaka Jumatatu mara tu uzembe ya orodha wanaohusishwa. Sisi ni nyuma na wakati linear. Hatuna tena safu contiguous. Hatuna random kupata. Hatuwezi kutumia mraba bracket nukuu. Sisi literally kuwa na matumizi ya kitanzi wakati kama moja niliandika wakati iliyopita. Lakini siku ya Jumatatu, sisi alidai kuwa tunaweza Baadhi yao huenda nyuma ndani ya eneo la ufanisi kufikia kitu ambacho ni logarithmic labda, au bora bado, labda hata kitu ambacho ni kinachojulikana wakati mara kwa mara. Hivyo ni jinsi gani tunaweza kufanya hivyo kwa kutumia hizi mpya zana, anwani hizi, kuyatumia haya, na threading mambo yetu wenyewe? Naam, tuseme kwamba hapa, haya ni rundo ya idadi ya kwamba tunataka kuhifadhi katika data ya muundo na utafutaji ufanisi. Tunaweza kabisa rewind kwa wiki mbili, kutupa hizi katika safu, na kutafuta yao kwa kutumia tafuta binary. Kugawanya na kushinda. Na kwa kweli aliandika tafuta binary katika PSET3, ambapo kutekelezwa kupata mpango. Lakini unajua nini. Kuna aina ya zaidi njia wajanja wa kufanya hivyo. Ni kidogo zaidi kisasa na labda inaruhusu sisi kuona nini binary search ni hivyo kwa kasi zaidi. Kwanza, hebu kuanzisha dhana ya mti. Ambayo hata kama katika miti ukweli aina ya kukua kama hii, katika dunia ya kompyuta sayansi wao aina ya kukua kushuka kama familia mti, ambapo una babu yako au mababu kubwa au whatnot juu, mfumo dume na matriarch wa familia, moja tu kinachojulikana mzizi, nodi, chini ambayo ni watoto wake, chini ambayo ni watoto wake, au kizazi wake zaidi kwa ujumla. Na mtu yeyote kunyongwa mbali Chini ya familia mti, badala ya kuwa mdogo katika familia, Unaweza pia tu kuwa yaliyotokea aitwaye majani ya mti. 

Hivyo hii ni tu rundo ya maneno na ufafanuzi kwa kitu kinachoitwa mti katika kompyuta sayansi, kiasi kama mti familia. Lakini kuna incarnations fancier ya miti, moja ambayo inaitwa binary tafuta mti. Na unaweza aina ya tease mbali nini jambo hili gani. Naam, ni mapacha katika maana gani? Wapi mapacha wanatoka hapa? Pole? Siyo sana ama au. Ni zaidi kwamba kila mmoja nodes hana watoto zaidi ya wawili, kama tunaona hapa. Kwa ujumla, tree-- na wazazi wako na mababu unaweza kuwa kama watoto wengi au grandkids kama kweli unataka, na hivyo kwa mfano pale tuna tatu watoto mbali kwamba nodi mkono wa kulia, lakini katika mti binary, nodi ina sifuri, moja, moja au mbili watoto maximally. Na hiyo ndiyo mali nzuri, kwa sababu kama ni ulimalizika kwa mbili, tunakwenda kuwa na uwezo wa kupata kidogo msingi gogo mbili hatua kinachoendelea hapa hatimaye. Hivyo tuna kitu logarithmic. Lakini zaidi juu ya kwamba katika wakati huu. Search mti ina maana kwamba idadi ni mpangilio kama kuwa mtoto wa kushoto wa thamani ni mkubwa kuliko mizizi. Na mtoto wake wa kulia ni kubwa kuliko mizizi. Kwa maneno mengine, kama wewe kuchukua yoyote ya nodes, duru katika picha hii, na inaangalia kushoto wake mtoto na mtoto wake wa kulia, kwanza wanapaswa kuwa chini ya, pili lazima kuwa kubwa kuliko. Hivyo sanity kuangalia 55. Ni kushoto mtoto ni 33. Ni chini ya. 55, mtoto wake wa kulia ni 77. Ni mkuu kuliko mimi. Na hiyo ndiyo ufafanuzi kujirudia. Tunaweza kuangalia kila mmoja wa wale nodes na mfano huo litaondoa. 

Kwa hiyo kile ni nzuri katika binary tafuta mti, ni kuwa moja, tunaweza kutekeleza na struct, tu kama hii. Na hata kama sisi ni kutupa kura ya miundo upande wako, wao uko kiasi fulani Intuitive sasa hopefully. Syntax bado ni arcane kwa hakika, lakini yaliyomo ya nodi katika hili context-- na tunaendelea kutumia neno nodi, kama ni Mstatili juu ya screen au mduara, ni baadhi tu ya chombo kurefusha maisha, katika kesi hii ya mti, kama moja tuliona, tunahitaji integer katika kila moja ya nodes na kisha nahitaji kuyatumia mbili akizungumzia kwa mtoto wa kushoto na mtoto wa kulia, mtawalia. Hivyo hiyo ni jinsi sisi anaweza kutekeleza kwamba katika struct. Na jinsi inaweza mimi kutekeleza katika kanuni? Naam, hebu kuchukua haraka tuangalie mfano huu vidogo. Siyo kazi, lakini nimekuwa kunakiliwa na pasted muundo huo. Na kama kazi yangu kwa mapacha la mti inaitwa utafutaji, na hii inachukua hoja mbili, integer N pointer na nodi, hivyo pointer mti au pointer mizizi ya mti, jinsi gani mimi kwenda kuhusu kutafuta N? Naam, kwanza, kwa sababu mimi nina kushughulika na kuyatumia, Mimi nina kwenda kufanya sanity hundi. Kama sawa mti sawa null, ni N katika mti huu au si katika mti huu? Haiwezi kuwa, haki? Kama mimi ni kipindi cha null, kuna kitu huko. Mimi ili kama vile tu upofu kusema kurudi uongo. Kama wewe nipe kitu, mimi hakika hawezi kupata idadi yoyote N. Hivyo kile kingine huenda mimi kuangalia sasa? Mimi nina kwenda kusema vizuri mwingine kama ni N chini ya chochote ni katika mti nodi kwamba nimekuwa mitupu thamani N. Kwa maneno mengine, kama idadi mimi nina kutafuta, N, ni chini ya nodi kwamba mimi nina kuangalia. Na node mimi nina kuangalia katika anaitwa mti, na kukumbuka kutoka mfano uliopita kupata katika thamani katika pointer, Mimi kutumia mshale nukuu. Hivyo kama N ni chini ya mti mshale N, nataka conceptually kwenda kushoto. Je, mimi kueleza na kutafuta kushoto? Kuwa wazi, kama hii ni picha katika swali, na nimekuwa kupita kwamba topmost mshale hiyo akizungumzia chini. Hiyo ni mti wangu pointer. Mimi akionyesha mizizi ya mti. Na mimi nina kuangalia kusema, kwa idadi 44, kiholela. Ni 44 chini ya au kubwa kuliko 55 ni wazi? Hivyo ni chini ya. Na hivyo hii kama hali inatumika. Hivyo conceptually, je, mimi nataka kutafuta ijayo kama mimi nina kuangalia kwa 44? Yeah? 

Hasa, nataka kutafuta mtoto wa kushoto, au kushoto ndogo ya mti wa picha hii. Na kwa kweli, napenda kupitia picha chini hapa kwa muda tu, kwani Siwezi scratch hii nje. Kama mimi kuanza hapa saa 55, na Najua kwamba thamani 44 Mimi nina kuangalia kwa ni kushoto, ni aina ya kama kuchanika kitabu cha simu katika nusu au kuchanika mti katika nusu. Mimi tena kuwa na huduma ya juu nusu huu mzima wa mti. Na bado, ajabu katika suala la muundo, jambo hili hapa kwamba huanza na 33, kwamba yenyewe ni binary tafuta mti. Nilisema neno kujirudia kabla kwa sababu Hakika hii ni muundo data kwamba kwa ufafanuzi ni kujirudia. Unaweza kuwa na mti huu ndiyo kubwa, lakini kila mmoja wa watoto wake inawakilisha mti kidogo tu vidogo vidogo. Badala ya kuwa babu au bibi, sasa ni tu mama or-- siwezi say-- si mama au baba, kwamba itakuwa weird. Badala watoto wawili huko itakuwa kama kaka na ndugu. Kizazi kipya wa mti familia. Lakini kimuundo, ni wazo moja. Na zinageuka nina kazi na ambayo siwezi kutafuta binary tafuta mti. Hiyo inaitwa utafutaji. Mimi kutafuta N katika mti mshale wa kushoto mwingine kama ni mkubwa kuliko N thamani kwamba mimi nina sasa katika. 55 katika hadithi wakati iliyopita. Nina kazi kuitwa search kwamba naweza tu kupita N huu na recursively kutafuta ndogo ya mti na kurudi tu chochote jibu hilo. Mwingine mimi nimepata baadhi ya kesi mwisho ya msingi hapa. 

Kesi ya mwisho ni nini? Mti ni aidha null. Thamani mimi nina ama kutafuta ni chini zaidi au mkubwa kuliko ule au sawa na hilo. Na mimi naweza kusema sawa sawa, lakini mantiki ni sawa na kusema tu kingine hapa. Hivyo kweli ni jinsi mimi kupata kitu. Hivyo hopefully hii ni mfano hata zaidi ya kulazimisha kuliko kijinga sigma kazi tulivyofanya mihadhara michache nyuma, ambapo ilikuwa ni kama rahisi kutumia kitanzi kwa kuhesabu hadi namba zote kutoka kwa mmoja na N. Hapa na muundo data kwamba yenyewe ni recursively inavyoelezwa na recursively inayotolewa, sasa sisi Una uwezo wa kueleza wenyewe katika kificho kwamba yenyewe ni kujirudia. Hivyo hii ni kamili kificho sawa hapa. 

Kwa hiyo kile matatizo mengine tunaweza kutatua? Hivyo hatua ya haraka mbali na miti kwa muda tu. Hapa ni, kusema, bendera ya Ujerumani. Na kuna wazi mfano kwa bendera hii. Na kuna kura ya bendera katika dunia ambayo ni rahisi kama hii katika suala ya rangi zao na mwelekeo. Lakini tuseme kwamba hii ni kuhifadhiwa kama GIF, JPEG au, au bitmap, au Ping, yoyote graphical faili na ambayo wewe ni ukoo, baadhi ya ambayo tuko kucheza na katika pset4. Hii haionekani vyema kuhifadhi nyeusi pixel, nyeusi pixel, nyeusi pixel, dot, dot, dot, kundi zima la saizi nyeusi kwa scanline kwanza, au mstari, basi kundi zima la sawa, basi kundi zima ya sawa, na kisha rundo zima la saizi nyekundu, saizi nyekundu, saizi nyekundu, kisha zima rundo la saizi njano, njano, sawa? 

Kuna uzembe kama hapa. Jinsi gani wewe shirikishi kubana bendera ya Ujerumani kama kuitekeleza kama jalada la? Kama ni habari tunaweza si kujisumbua kuhifadhi kwenye disk ili kupunguza ukubwa faili wetu kutoka kama megabyte kwa kilobaiti, kitu kubwa? Eti lipo redundancy hapa kuwa wazi? Je, inaweza kufanya nini? Yeah? Hasa. Kwa nini badala ya kukumbuka rangi ya kila pixel darn kama unafanya katika pset4 na bitmap faili, kwa nini sio wewe tu kuwakilisha leftmost safu ya saizi, kwa mfano rundo la saizi nyeusi, rundo ya nyekundu, na kundi la njano, na kisha tu kwa namna fulani encode wazo la kurudia hii mara 100 au kurudia hii mara 1,000? Ambapo 100 au 1000 ni tu integer, hivyo wanaweza kuondokana na tu namba moja badala ya mamia au maelfu saizi ya ziada. Na hakika, hiyo ni jinsi sisi inaweza kubana bendera ya Ujerumani. Na Sasa vipi kuhusu bendera Kifaransa? Na kidogo baadhi ya aina ya mazoezi ya akili, ambayo bendera inaweza kuwa Komprimerade zaidi ya rekodi? Bendera ya Ujerumani au Ufaransa bendera, kama sisi kuchukua mtazamo huo? Bendera ya Ujerumani, kwa sababu kuna zaidi usawa redundancy. Na kwa kubuni, wengi graphical faili miundo kwa hakika kazi mistari kama scan usawa. Wangeweza kufanya kazi wima, ubinadamu tu Miaka aliamua iliyopita kwamba tutaweza ujumla kufikiria mambo mstari na mstari badala ya safu kwa safu. Hivyo kweli kama ungekuwa kuangalia faili ukubwa wa bendera ya Ujerumani na Ufaransa bendera, hivyo muda mrefu kama azimio ni huo, upana huo na urefu, hii ni moja hapa ni kwenda kuwa kubwa zaidi, kwa sababu wewe kurudia mwenyewe mara tatu. Una bayana bluu, kurudia mwenyewe, nyeupe, kurudia mwenyewe, nyekundu, kurudia mwenyewe. Huwezi tu kwenda wote njia ya haki. Na kama kando, ili kufanya wazi compression ni kila mahali, kama haya ni muafaka nne kutoka video-- wewe Huenda unakumbuka kwamba movie video ujumla kama 29 au 30 muafaka kwa pili. Ni kama kidogo flip kitabu ambapo tu kuona picha, picha, picha, picha, picha tu super haraka hivyo inaonekana kama watendaji kwenye screen ni kusonga mbele. Hapa ni nyuki bumble juu ya juu ya rundo la maua. Na ingawa inaweza kuwa aina ya vigumu kuona katika mtazamo wa kwanza, Kitu pekee kusonga katika sinema hii ni nyuki. 

Je, ni bubu kuhusu hifadhi video uncompressed? Ni aina ya taka kuhifadhi video kama nne picha karibu kufanana kwamba tofauti tu kadiri ambapo nyuki ni. Unaweza kutupa mbali zaidi wa habari kwamba na kumbuka tu, kwa mfano, sura ya kwanza na sura ya mwisho, muafaka muhimu kama wameweza umewahi kusikia neno, na tu kuhifadhi katika katikati ambapo nyuki ni. Na wewe huna kuhifadhi wote wa nyekundu, na bluu, na maadili ya kijani pia. Hivyo hii ni kusema tu kwamba compression ni kila mahali. Ni mbinu sisi mara nyingi kutumia au kuchukua kwa nafasi siku hizi. 

Lakini jinsi gani unaweza compress maandishi? Jinsi gani unaweza kwenda juu compressing maandishi? Naam, kila mmoja wa wahusika katika Ascii ni byte moja, au bits nane. Na hiyo ni aina ya bubu, sawa? Kwa sababu wewe pengine aina A na E na mimi na O na U mengi mara nyingi zaidi kuliko kama W au Swali au Z, kutegemea lugha ambayo wewe ni kuandika bila ya shaka. Na hivyo kwa nini sisi kutumia bits nane kwa kila barua, ikiwa ni pamoja na uchache barua maarufu, sawa? Kwa nini matumizi ya vipande wachache kwa barua super maarufu, kama E, mambo wewe nadhani kwanza katika gurudumu la Bahati, na kutumia bits zaidi kwa chini maarufu barua? Kwa nini? Kwa sababu tunakwenda tu kwa kuzitumia kidogo mara kwa mara. 

Naam, ni zamu nje kwamba kuna wana Imekuwa majaribio alifanya kufanya hivyo. Na kama unakumbuka kutoka daraja shule au shule ya sekondari, kanuni Morse. Morse ina nukta na dashes ambayo inaweza kuwa zinaa pamoja waya kama sauti au ishara ya aina fulani. Lakini kanuni Morse ni super safi. Ni aina ya mfumo wa binary katika kwamba una nukta au dashes. Lakini kama unaweza kuona, kwa mfano, nukta mbili. Au kama unadhani nyuma operator ambao unaendelea kama beep, beep, beep, beep, kupiga trigger kidogo inayoambukiza ishara, kama wewe, mpokeaji, inapata mbili dots, nini ujumbe kuwa umepokea? Kabisa holela. 

I? I? Au about-- nini au mimi? Labda ilikuwa miwili tu E ya haki? Hivyo kuna tatizo hili ya decodability na Morse kificho, ambapo isipokuwa mtu kutuma ujumbe kweli anapo hivyo unaweza aina ya kuona au kusikia mapengo kati ya herufi, siyo wa kutosha tu kutuma mkondo wa zeros na ndio, au dots na dashes, kwa sababu kuna utata. E ni moja nukta, hivyo kama wewe ona nukta mbili au kusikia nukta mbili, labda ni E mbili ya au labda ni mimi moja Kwa hiyo, tunahitaji mfumo huo ambao zaidi kidogo wajanja kuliko hiyo. Hivyo mtu mmoja aitwaye Huffman miaka iliyopita alikuja na hasa hili. Hivyo sisi ni kwenda tu kuchukua mtazamo wa haraka jinsi miti ni germane na hii. Tuseme kwamba hii ni baadhi kijinga ujumbe unataka kutuma, linajumuisha tu A, B, C D's na E wa, lakini kuna mengi ya redundancy hapa. Siyo maana ya kuwa Kiingereza. Siyo siri. Ni tu ujumbe wa kijinga kwa kura ya marudio. Kweli Hivyo kama wewe kuhesabu nje wote Wa, B, C, D's, na E ya, hapa ni mzunguko. 20% ya barua ni Wa, 45% ya barua ni E, na masafa wengine watatu. Sisi kuhesabiwa hadi pale kwa mikono na tu alifanya hisabati. 

Hivyo zinageuka kuwa Huffman, baadhi ya wakati uliopita, waligundua kuwa, unajua nini, kama mimi kuanza kujenga mti, au msitu wa miti, kama wewe, kama ifuatavyo, siwezi kufanya yafuatayo. Mimi nina kwenda kutoa nodi ya kila wa barua kwamba mimi huduma ya juu na mimi nina kwenda kuhifadhi ndani ya nodi masafa kama hatua yaliyo thamani, au unaweza kuitumia N, pia, lakini tutaweza tu kutumia kuelea hapa. Na algorithm kwamba alipendekeza ni kwamba kuchukua msitu huu wa nodi moja miti, miti ili super mfupi, na kuanza kuunganisha yao na vikundi vipya, wazazi mpya, kama wewe. Na wewe kufanya hivyo kwa kuchagua masafa mbili ndogo wakati huo. Hivyo mimi alichukua 10% na 10%. Mimi kujenga nodi mpya. Na mimi wito nodi mpya 20%. 

Ambayo nodes mbili mimi kuchanganya baada ya hapo? Ni kidogo utata. Hivyo kuna baadhi ya matukio kona ya kufikiria, lakini kuweka mambo pretty, Mimi nina kwenda kuchagua 20% - Mimi sasa kupuuza watoto. Mimi nina kwenda kuchagua 20% na 15% na kuteka kuwili mpya. Na sasa ambayo nodes mbili Je, mimi kifikra kuchanganya? Kupuuza watoto wote, kila wajukuu, tu kuangalia mizizi sasa. Ambayo nodes mbili do I kufunga pamoja? Point mbili na 0.35. Hivyo basi mimi kuteka kuwili mpya. Na kisha nimekuwa tu got moja wa kushoto. Hivyo hapa ni mti. Na imekuwa ni inayotolewa kwa makusudi kuangalia namna ya warembo, lakini taarifa kwamba kingo na pia kimepewa jina la sifuri na moja. Basi wote wa kushoto kingo ni sifuri kiholela, lakini mara kwa mara. Kingo zote haki ndio. 

Na hivyo kile Hoffman mapendekezo ni, kama unataka kuwakilisha B, badala ya kuwakilisha idadi 66 kama Ascii ambayo ni nane bits nzima, unajua nini, tu duka mfano sifuri, sifuri, sifuri, sifuri, kwa sababu hiyo ni njia kutoka mti wangu, mti Mheshimiwa Huffman wa, kwa jani kutoka mizizi. Kama unataka kuhifadhi E, kwa kulinganisha, hawana kutuma bits nane kwamba kuwakilisha E. Badala yake, kutuma mfano gani wa bits? Moja. Na nini ni nzuri kuhusu hili ni kwamba E ni barua maarufu, na unatumia mfupi kificho kwa hilo. Ijayo maarufu barua inaonekana kama ni ilikuwa A. Na hivyo jinsi wengi bits yeye kupendekeza kutumia kwa kufanya hivyo? Sifuri, moja. 

Na kwa sababu ni kutekelezwa kama mti huu, kwa sasa napenda inasema kuna hakuna utata kama katika Morse kanuni, kwa sababu yote ya barua unaowajali ni mwishoni mwa kingo hizo. Hivyo hiyo ni moja maombi ya mti. Hii is-- na mimi itabidi kukitikisa mkono wangu katika hii jinsi inaweza kutekeleza hili kama C muundo. Sisi tu haja ya kuchanganya ishara, kama Char, na mzunguko katika kushoto na kulia. Lakini hebu tuangalie mbili mifano ya mwisho kwamba utasikia kupata kabisa na mazoea na baada ya Jaribio sifuri katika tatizo kuweka tano. 

Kwa hiyo, kuna muundo wa data inayojulikana kama meza hash. Na meza hash ni aina ya baridi kwa kuwa ina ndoo. Na tuseme kuna ndoo nne hapa, nafasi nne tu tupu. Hapa ni karata, na hapa ni klabu, jembe, klabu, almasi, klabu, almasi, klabu, almasi, clubs-- hivyo hii ni random. Mioyo, hearts-- hivyo mimi nina bucketizing wote wa pembejeo hapa. Na mahitaji hash meza kuangalia mchango wako, na kisha kuiweka katika baadhi ya mahali kulingana na nini kuona. Ni algorithm. Na nilikuwa kutumia super rahisi Visual algorithm. Sehemu ya gumu ya ambayo ilikuwa kukumbuka kile picha walikuwa. Na kisha kuna mambo manne jumla. 

Sasa mwingi walikuwa kupanda, ambayo ni makusudi kubuni kitu hapa. Lakini kile kingine inaweza nifanye nini? Hivyo kweli hapa tuna kundi la umri wa vitabu mtihani shule. Tuseme kwamba kundi la wanafunzi majina yao ni juu ya hapa. Hapa ni kubwa hash meza. Badala ya ndoo nne, I have, hebu sema 26. Na hatukutaka kwenda kukopa 26 mambo kutoka nje [? Annenberg?], Hivyo hapa ni tano ambazo kuwakilisha Kupitia Z. Na kama mimi ona mwanafunzi ambaye jina lake huanza na, Mimi nina kwenda kuweka wake au jaribio yake huko. Kama mtu huanza na C, zaidi ya hapo, A-- kweli, sitaki kufanya hivyo. B huenda zaidi ya hapa. Hivyo mimi nimepata A na B na C. Na sasa hapa mwingine A mwanafunzi. Lakini kama hii meza hash ni kutekelezwa na safu, Mimi aina ya Star katika hatua hii, sawa? Mimi aina ya haja ya kuweka mahali fulani huu. 

Hivyo njia moja siwezi kutatua hili ni, kila haki, A ni busy, B ni busy, C ni busy. Mimi nina kwenda kumtia D. Hivyo katika kwanza, nina random kupata papo kwa kila mmoja wa ndoo kwa wanafunzi. Lakini sasa ni aina ya ugatuzi katika kitu linear, kwa sababu kama nataka kutafuta mtu jina lake huanza na A, mimi kuangalia hapa. Lakini kama hii si A mwanafunzi Mimi nina kuangalia kwa, Mimi aina ya kuwa na kuanza kuangalia ndoo, kwa sababu nini mimi ilikuwa ni aina ya mstari kuchunguza muundo wa data. Njia kijinga ya kusema tu kuangalia kwa kwanza inapatikana ufunguzi, na kuweka kama mpango B, hivyo kusema, au mpango D katika kesi hiyo, thamani katika eneo hilo badala yake. Hii ni hivyo tu kwamba kama wameweza got maeneo 26 na hakuna wanafunzi kwa jina Swali au Z, au kitu kama kwamba, angalau unatumia nafasi. 

Lakini tumekuwa tayari kuona zaidi ufumbuzi wajanja hapa, sawa? Je utafanya nini badala kama una mgongano? Kama watu wawili na jina A, gani wamekuwa nadhifu au zaidi Intuitive ufumbuzi kuliko tu kuweka A ambapo D zinatakiwa kuwa? Mbona mimi tu kwenda nje [? Annenberg?], kama malloc, nodi mwingine, kuiweka hapa, na kisha kuweka kwamba mwanafunzi hapa. Ili niweze kimsingi kuwa baadhi ya aina ya safu, au labda elegantly zaidi kama tuko mapya ya kuona orodha wanaohusishwa. 

Na hivyo meza hash ni muundo ambayo inaweza kuangalia kama hii, lakini zaidi kwa uwazi, wewe kitu kinachoitwa tofauti chaining, ambapo meza hash rahisi kabisa ni safu, kila mmoja ambao mambo si idadi, ni yenyewe orodha wanaohusishwa. Ili uweze kupata super haraka kuamua wapi pa hash thamani yako kwa. Kiasi kama na kadi mfano, Mimi alifanya maamuzi super haraka. Mioyo huenda hapa, almasi huenda hapa. Sawa hapa, A huenda hapa, D unaendelea hapa, B huenda hapa. Hivyo super haraka kuangalia-ups, na kama kutokea kwa kukimbia katika kesi ambapo nimepata migongano, wawili watu wenye jina moja, vizuri basi wewe tu kuanza kuwaunganisha pamoja. Na labda wewe kuwaweka yamepangwa alphabetically, labda huna. Lakini angalau sasa tuna mabadiliko. Hivyo kwa upande mmoja tuna super haraka wakati mara kwa mara, na aina ya muda linear waliohusika ikiwa orodha hizi wanaohusishwa kuanza kupata kidogo kwa muda mrefu. 

Hivyo aina hii ya kijinga, geeky utani miaka iliyopita. Wakati CS50 hack-thon, wakati wanafunzi angalia katika, baadhi TF au CA kila mwaka anadhani ni funny kuweka ishara kama hii, ambapo ni tu ina maana kama jina lako huanza na A, kwenda kwa njia hii. Kama jina yako kuanza na B, kwenda Haya Sawa, ni funny labda baadaye katika muhula. Lakini kuna mwingine njia ya kufanya hivyo, pia. Kuja nyuma na kwamba. 

Hivyo kuna muundo huu. Na hii ni mwisho wetu muundo wa leo, ambayo ni kitu kinachoitwa trie. T-R-I-E, ambayo kwa sababu baadhi ni fupi kwa retrieval, lakini ni kuitwa trie. Hivyo trie ni mwingine kuvutia amalgam wa mengi ya mawazo haya. Ni mti, ambayo tumeona kabla. Siyo binary tafuta mti. Ni mti na idadi yoyote ya watoto, lakini kila mmoja wa watoto katika trie ni safu. Safu ya ukubwa, kusema, 26 au labda 27 kama unataka kusaidia majina hyphenated au apostrophes katika majina ya watu. 

Na hivyo hii ni muundo data. Na kama ukiangalia toka juu hadi chini, kama kama wewe kuangalia nodi juu huko, M, ni akizungumzia jambo leftmost huko, ambayo ni kisha A, X, W, E, L, L. Hii ni tu mfumo wa takwimu ambazo kiholela ni kuhifadhi majina ya watu. Na Maxwell ni kuhifadhiwa kwa kufuata tu njia ya safu kwa safu kwa safu. Lakini nini ajabu kuhusu trie ni ili, iwapo orodha wanaohusishwa na hata safu, bora tumekuwa milele wamezipata ni muda linear au wakati logarithmic kuangalia mtu up. Katika muundo huu data ya trie, ikiwa muundo yangu data ina jina moja ndani yake na mimi nina kuangalia kwa Maxwell, mimi nina kwenda kumpata pretty haraka. Mimi tu kuangalia kwa M-A-X-W-E-L-L. Kama muundo huu data, kwa kulinganisha, kama ni milioni N, kama kuna milioni majina katika muundo huu data, Maxwell bado ni kwenda kuwa iweze baada tu M-A-X-W-E-L-L hatua. Na David-- D-A-V-I-D hatua. Kwa maneno mengine, kwa kujenga muundo wa data hiyo ni got wote wa arrays haya, ambayo yote wenyewe kusaidia upatikanaji random, Siwezi kuanza kuangalia juu ya watu jina kwa kutumia kiasi cha muda kwamba sawia na si idadi mambo katika muundo data, kama milioni majina zilizopo. Kiasi cha muda inachukua mimi kupata M-A-X-W-E-L-L katika muundo huu data ni sawia si kwa ukubwa wa muundo data, lakini kwa urefu wa jina. Na realistically majina sisi ni kuangalia up ni kamwe kwenda kuwa mambo kwa muda mrefu. Labda mtu ana 10 tabia jina, 20 jina tabia. Ni hakika mahususi, sawa? Kuna binadamu duniani ambao ina jina mrefu iwezekanavyo, lakini jina kwamba ni mara kwa mara thamani urefu, sawa? Ni haina kutofautiana kwa maana yoyote. Hivyo kwa njia hii, tumekuwa mafanikio ya muundo data kwamba ni wakati wa mara kwa mara kuangalia-up. Ni gani kuchukua idadi ya hatua kulingana na urefu wa pembejeo, lakini si hesabu ya jina katika muundo data. Hivyo kama sisi mara mbili ya idadi ya majina mwaka ujao kutoka bilioni bilioni mbili, kutafuta Maxwell ni kwenda kuchukua exact idadi ya hatua saba kumpata. Na hivyo sisi wanaonekana kuwa na mafanikio grail takatifu ya yetu mbio wakati. 

Hivyo wanandoa wa matangazo ya haraka. Jaribio sifuri ni kuja juu. Zaidi juu ya kwamba kwenye tovuti kozi ya zaidi ya michache ijayo siku. Jumatatu lecture-- ni likizo hapa katika Harvard siku ya Jumatatu. Siyo katika New Haven, hivyo sisi ni kuchukua darasa kwa New Haven kwa hotuba siku ya Jumatatu. Kila kitu itakuwa zingine na mkondo moja kwa moja kama kawaida, lakini hebu mwisho leo na 30 kipande cha pili inayoitwa "Deep Mawazo" na Daven Farnham, ambayo ulitokana mwaka jana na Saturday Usiku Mpya ya "Deep Mawazo" na Jack Sehemu, ambayo lazima sasa mantiki. 

FILM: Na sasa, "Deep Mawazo "na Daven Farnham. Meza hash. 

SPIKA 1: zote haki, hiyo ni yake kwa sasa. Tutaweza kuona wewe wiki ijayo. 

DOUG: Kwa kuona katika hatua. Basi hebu tuangalie kwamba hivi sasa. Hivyo hapa, tuna safu zisizochambuliwa. 

Ian: Doug, unaweza kwenda mbele na kuanzisha upya huu kwa moja tu ya pili, tafadhali. Haki wote, kamera ni rolling, hivyo hatua wakati wowote uko tayari, Doug, sawa? DOUG: zote haki, hivyo kile sisi na hapa ni safu zisizochambuliwa. Na nimekuwa rangi wote wa mambo nyekundu zinaonyesha kwamba ni, kwa kweli, zisizochambuliwa. Hivyo kukumbuka kwamba jambo la kwanza sisi kufanya ni sisi kuchambua kushoto nusu ya safu. Kisha sisi kutatua haki nusu ya safu. Na ya-da, da ya-, ya-da, sisi kuunganisha pamoja. Na tuna safu Iliyopangwa kabisa. Hivyo hiyo ni jinsi kuunganisha aina kazi. 

Ian: Whoa, Ho, Ho, kata, kata, kata, kata. Doug, huwezi ya-da tu, ya-da, ya-da, njia yako kwa njia ya aina kuunganisha. 

DOUG: Mimi tu alivyofanya. Ni faini. Sisi ni vizuri kwenda. Hebu tu kushika rolling. Hivyo anyway, 

Ian: Una kueleza kikamilifu zaidi kuliko hiyo. Hiyo tu haitoshi. DOUG: Ian, hatufanyi haja ya kwenda nyuma ya moja. Ni faini. Hivyo anyway, tukiendelea na merge-- Ian, tuko katikati ya sinema. 

Ian: Mimi najua. Na hatuwezi ya-da tu, ya-da, ya-da, kupitia mchakato mzima. Una kueleza jinsi pande hizo mbili kupata zimeunganishwa pamoja. 

DOUG: Lakini tumekuwa tayari alielezea jinsi sides-- mbili 

Ian: Ve tu umeonyesha nao kuunganisha safu. DOUG: Wanajua mchakato. Wao ni faini. Tumeenda juu yake mara kumi. 

Ian: Wewe tu skipped haki juu yake. Tunakwenda nyuma moja, wewe hawezi wewe ya-da, da ya-juu yake. Haki wote, nyuma moja. 

DOUG: Mimi kuwa na kurejea njia zote za slides? Mungu wangu. Ni kama mara ya sita, Ian. Ni faini. 

Ian: zote haki. Uko tayari? Kubwa. Action.