DOUG LLOYD: Kwa hiyo katika CS50, tumekuwa kufunikwa mengi ya miundo tofauti data, sawa? Tumeona arrays, na wanaohusishwa orodha, na meza hash, na inajaribu, mwingi na foleni. Tutaweza pia kujifunza kidogo kuhusu miti na magofu, lakini kwa kweli haya yote tu kuishia up kuwa tofauti juu ya mandhari. Kuna kweli ni haya aina ya mawazo nne za msingi kwamba kila kitu kingine unaweza jipu chini kwa. Arrays, wanaohusishwa orodha, meza hash, na inajaribu. Na kama nilivyosema, kuna ni tofauti juu yao, lakini hii ni pretty mengi kwenda muhtasari kila kitu sisi ni kwenda kuzungumza kuhusu katika darasa hili katika suala la C. Lakini ni jinsi gani haya yote hatua up, sawa? Tumekuwa aliyesema kuhusu faida na hasara wa kila katika video tofauti juu yao, lakini kuna mengi ya idadi kupata kutupwa kuzunguka. Kuna mengi ya ujumla mawazo kupata kutupwa kuzunguka. Hebu jaribu na kuimarisha ni katika nafasi moja tu. Hebu kupima faida dhidi ya hasara, na kufikiria ambayo muundo wa data inaweza kuwa data sahihi muundo kwa hali yako maalum, chochote aina ya data wewe ni hifadhi. Wewe si lazima daima haja ya kutumia super haraka kuingizwa, kufutwa, na chaguo-ya trie kama kweli hawajali kuingiza na kufuta imezidi. Kama unahitaji haraka tu bila mpangilio upatikanaji, labda safu ni bora zaidi. Basi hebu distill hiyo. Hebu majadiliano juu ya kila moja ya nne aina kuu ya miundo data kwamba tumekuwa kuongelea, na tu kuona wakati wao inaweza kuwa nzuri, na wakati wao wanaweza kuwa hivyo nzuri. Basi hebu kuanza na arrays. Hivyo kuingizwa, hiyo ni aina ya mbaya. 

Kuingizwa mwishoni mwa safu ni sawa, kama sisi ni kujenga safu kama sisi kwenda. Lakini kama sisi haja ya kuingiza mambo ndani ya katikati, kufikiri nyuma kuingizwa aina, kuna mengi ya kuhama na kifafa kipengele katika huko. Na hivyo kama tunakwenda kuingiza mahali popote lakini mwisho wa safu, kwamba pengine si kubwa sana. 

Vile vile, kufutwa, isipokuwa tuko kufuta kutoka mwisho wa safu, pengine pia si kubwa sana kama hatutaki kuondoka mapengo tupu, ambayo kwa kawaida hatuna. Tunataka kuondoa kipengele, na kisha aina ya kufanya hivyo snug tena. Na hivyo kufuta vipengele kutoka safu, pia si kubwa sana. 

Luke, ingawa, ni kubwa. Tuna upatikanaji random, mara kwa mara wakati Luke. Sisi tu kusema saba, na sisi kwenda kwa safu kuhamishwa saba. Tunasema 20, na kwenda kwa safu kuhamishwa 20. Hatuna iterate hela. Hiyo ni nzuri sana. 

Arrays ni pia rahisi kutatua. Kila wakati sisi aliyesema kuhusu kuchagua algorithm, kama vile uteuzi aina, kuingizwa aina, Bubble aina, kuunganisha aina, sisi daima kutumika arrays ya kufanya hivyo, kwa sababu arrays ni rahisi sana aina, jamaa na miundo data tumeona hadi sasa. 

Wao ni pia kiasi kidogo. Kuna si mengi ya nafasi ya ziada. Wewe tu kuweka kando hasa kama kiasi kama unahitaji kushikilia data yako, na kwamba ni pretty kiasi. Hivyo wao ni pretty ndogo na ufanisi katika njia hiyo. Lakini upande wa chini jingine, ingawa, ni kwamba wao ni fasta katika kawaida. Tuna kutangaza hasa jinsi kubwa tunataka safu yetu kuwa, na sisi tu kupata risasi moja katika hilo. Hatuwezi kukua na kuogopa hilo. 

Kama tunahitaji kukua au kuogopa hilo, sisi haja ya kutangaza safu mpya kabisa, nakala zote za mambo ya safu ya kwanza katika safu ya pili. Na kama sisi miscalculated kwamba muda, sisi haja ya kufanya hivyo tena. Si kubwa sana. Hivyo arrays si kutupa kubadilika kuwa na idadi kutofautiana wa mambo. 

Kwa orodha wanaohusishwa, kuingizwa ni rahisi sana. Sisi tu upepo kwenye mbele. Kufutwa pia ni rahisi sana. Tuna kupata vipengele. Ambazo zinahusisha baadhi kutafuta. 

Lakini mara Nimepata kipengele wewe kutafuta, wote unahitaji kufanya ni mabadiliko pointer, uwezekano mbili kama una wanaohusishwa list-- mara mbili orodha wanaohusishwa, rather-- na kisha unaweza tu bure nodi. Huna kuhama kila kitu karibu. Wewe tu mabadiliko kuyatumia mbili, hivyo hiyo ni pretty haraka. 

Luke ni mbaya ingawa, sawa? Ili na sisi kupata kipengele katika orodha wanaohusishwa, kama moja moja au mara mbili wanaohusishwa, tuna linear tafuta yake. Tuna kuanza mwanzoni na hoja ya mwisho, au kuanza mwishoni mwa hoja kwa mwanzo. Hatuna random kupata tena. Hivyo kama sisi ni kufanya mengi ya kutafuta, labda orodha wanaohusishwa sio kabisa hivyo nzuri kwetu. 

Wao ni pia kweli vigumu kutatua, sawa? Njia pekee unaweza kweli aina orodha wanaohusishwa ni ya aina hiyo kama wewe kujenga yake. Lakini kama wewe aina yake kama wewe kujenga ni, wewe ni tena kufanya insertions haraka tena. Wewe si tu tacking mambo kwenye mbele. Una kupata doa haki na kuiweka, na kisha kuingizwa yako inakuwa tu kuhusu kama mbaya kama kuingiza ndani ya safu. Hivyo orodha wanaohusishwa si kubwa sana kwa ajili ya kuchagua data. 

Wao ni pia pretty ndogo, ukubwa-busara. Doubly wanaohusishwa orodha kidogo kubwa kuliko orodha moja moja wanaohusishwa, ambayo ni kubwa kidogo kuliko arrays, lakini siyo kiasi kikubwa cha kupita nafasi. Hivyo kama nafasi ni katika premium, lakini si malipo kweli makali, hii inaweza kuwa njia sahihi ya kwenda. 

Hash meza. Kuingizwa katika meza hash ni haki moja kwa moja. Ni mchakato wa hatua mbili. Kwanza tunahitaji kukimbia takwimu zetu kupitia heshi kupata hash kificho, na kisha sisi kuingiza kipengele katika hash meza wakati huo hash kificho eneo. 

Kufutwa, sawa na orodha wanaohusishwa, Ni rahisi mara moja kupata kipengele. Una kupata hiyo kwanza, lakini kisha wakati wewe kufuta, wewe tu haja ya kubadilishana michache ya kuyatumia, kama unatumia tofauti chaining. Kama unatumia uchunguzi, au kama huna kutumia chaining wakati wote katika hash meza yako, kufutwa ni kweli kweli ni rahisi. Wote unahitaji kufanya ni hash data, na kisha kwenda eneo hilo. Na kuchukua huna na migongano yoyote, wewe utakuwa na uwezo wa kufuta haraka sana. 

Sasa, chaguo-ndipo mambo kupata ngumu zaidi kidogo. Ni kwa wastani bora kuliko orodha wanaohusishwa. Kama unatumia chaining, bado una orodha wanaohusishwa, ambayo ina maana bado una search hasara orodha wanaohusishwa. Lakini kwa sababu wewe ni kuchukua wanaohusishwa yako orodha na kuigawanya zaidi ya 100 au 1000 au n vipengele katika hash meza yako, wewe ni orodha wanaohusishwa wote ni kitu kimoja nth ukubwa. Wao ni wote kikubwa ndogo. Una n wanaohusishwa orodha badala ya moja wanaohusishwa orodha ya ukubwa n. 

Na hivyo halisi ya dunia hii mara kwa mara sababu, ambayo sisi ujumla wala majadiliano kuhusu muda utata, ni haina kweli kufanya tofauti hapa. Hivyo chaguo-bado linear kutafuta kama unatumia chaining, lakini urefu wa orodha wewe ni kutafuta njia ya ni sana, muda mfupi sana kwa kulinganisha. Tena, kama kuchagua ni yako lengo hapa, hash meza ya pengine si njia sahihi ya kwenda. Tu kutumia safu kama kuchagua ni kweli ni muhimu na wewe. 

Na wanaweza inataka wa kawaida. Ni vigumu kusema kama hash meza ni ndogo au kubwa, kwa sababu ni kweli inategemea jinsi kubwa hash meza yako ni. Kama wewe ni tu kwenda kuwa hifadhi mambo matano katika hash meza yako, na una meza hash na mambo 10,000 ndani yake, pengine wewe kupoteza nafasi kubwa mno. Tofauti kuwa unaweza pia na meza hash kompakt sana, lakini ndogo hash meza yako anapata, tena kila moja ya orodha wanaohusishwa wale anapata. Na hivyo kuna kweli hakuna njia kufafanua hasa ukubwa wa meza hash, lakini pengine salama kusema ni kwa ujumla kwenda kuwa kubwa kuliko wanaohusishwa orodha kuhifadhi data huo huo, lakini ndogo kuliko trie. 

Na inajaribu ni ya nne ya miundo haya kwamba sisi tumekuwa kuzungumza juu. Kuingiza katika trie ni ngumu. Kuna mengi ya nguvu mgao kumbukumbu, hasa mwanzoni, kama wewe ni mapya ya kujenga. Lakini ni wakati wa mara kwa mara. Ni tu kipengele binadamu hapa kwamba inafanya gumu. Kuwa na kukutana na pointer null, malloc nafasi, kwenda huko, nafasi uwezekano malloc kutoka huko tena. Aina ya vitisho sababu ya kuyatumia katika mgao wa nguvu kumbukumbu ni tatizo kwa wazi. Lakini mara moja umefanya akalipa yake, kuingizwa kweli ilitokana rahisi, na ni hakika ni wakati wa mara kwa mara. 

Kufutwa ni rahisi. Wote unahitaji kufanya ni navigate chini michache ya kuyatumia na nodi bure, hivyo hiyo ni nzuri sana. Luke pia ni pretty kufunga. Ni msingi tu juu ya urefu wa data zako. Hivyo kama wote wa taarifa yako ni masharti tano tabia, Kwa mfano, wewe ni hifadhi tano masharti tabia katika trie yako, tu inachukua hatua tano kupata nini wewe kutafuta. Tano ni sababu mara kwa mara, hivyo tena, kuingizwa, kufutwa, na chaguo- hapa ni wakati wote mara kwa mara, kwa ufanisi. 

Kitu kingine ni kwamba trie yako ni kweli aina ya tayari Iliyopangwa, sawa? Kwa mujibu wa jinsi tuko kuingiza vipengele, kwa kwenda barua na barua ya ufunguo, au tarakimu na tarakimu la muhimu, kawaida, trie yako kuishia kuwa aina ya yamepangwa kama kujenga yake. Haina kweli hufanya maana kufikiri juu ya kuchagua katika njia hiyo sisi kufikiri juu ya kwa arrays, au orodha wanaohusishwa, au meza hash. Lakini katika baadhi ya hisia, yako trie ni yamepangwa kama wewe kwenda. 

Upande mwingine, bila shaka, ni kwamba trie haraka inakuwa kubwa. Kutoka kila hatua ya makutano, waweza have-- kama ufunguo wako lina tarakimu, una 10 wengine maeneo unaweza kwenda, ambayo maana yake ni kwamba kila node ina taarifa kuhusu data unataka kuhifadhi wakati huo nodi, pamoja na kuyatumia 10. Ambayo, juu ya CS50 IDE, ni 80 ka. Hivyo ni angalau 80 ka kwa kila nodi kwamba kujenga, na kwamba hata kuhesabu data. Na kama nodes yako ni barua badala ya tarakimu, sasa una 26 kuyatumia kutoka kila eneo. Na 26 mara 8 pengine 200 ka, au kitu kama hicho. Na una mtaji na lowercase-- unaweza kuona ambapo mimi nina kwenda na hii, sawa? Nodes wako anaweza kupata kweli kubwa, na hivyo trie yenyewe, kwa ujumla, unaweza kupata kweli kubwa, pia. Hivyo kama nafasi ni katika mwendo wa premium kwenye mfumo wako, trie wanaweza kuwa njia sahihi ya kwenda, ingawa faida zake nyingine kuja kucheza. Mimi nina Doug Lloyd. Hii ni CS50.