Oratè 1: Tout dwa, se konsa nou yo tounen. Byenveni nan CS50. Sa a se fen semèn sèt. Se konsa, sonje tan sa a sot pase yo, nou te kòmanse gade nan yon ti kras sofistike plis done estrikti. Depi moute jouk koulye a, tout nou te gen reyèlman a jete nou an te sa a, yon etalaj. Men, anvan nou jete etalaj la kòm pa tout sa ki enteresan, ki tout bon li aktyèlman se, ki sa ki yo se kèk nan la pluses sa a done ki senp estrikti konsa byen lwen? Ki sa ki nan li bon an? Se konsa, lwen jan nou te wè? Ki sa ki ou te resevwa? Pa gen anyen. ELÈV: [fèbl]. Oratè 1: Ki sa ki nan sa? ELÈV: [fèbl]. Oratè 1: fiks gwosè. OK, Se konsa, poukisa se gwosè fiks bon menm si? ELÈV: [fèbl]. Oratè 1: OK, se konsa li efikas nan sans ke ou ka asiyen yon fiks kantite lajan pou espas, ki èspere ke se jisteman kòm anpil espas jan ou vle. Se konsa, ki ta ka absoliman yon plis. Ki sa ki nan yon lòt bò leve nan yon etalaj? Yeah? ELÈV: [fèbl]. Oratè 1: Tout - regrèt a? ELÈV: [fèbl]. Oratè 1: Tout bwat yo nan memwa oswa pwochen youn ak lòt. Epi sa a, itil - pou kisa? Sa a afè vre. Men, ki jan nou ka esplwate ke verite? ELÈV: [fèbl]. Oratè 1: Egzakteman, nou ka kenbe tras nan kote tout bagay se jis pa konnen yon sèl adrès, sètadi adrès la nan la premye multiple nan ki ti moso nan memwa. Oswa nan ka a nan fisèl la, adrès la nan premye a Char nan ki fil. Li te pran depi la, nou ka jwenn nan fen fisèl la. Nou ka jwenn eleman ki, dezyèm lan, twazyèm eleman, ak pou fè. Se konsa, wout la anpenpan nan ki dekri ki karakteristik se ke ranje ban nou o aza aksè. Jis lè l sèvi avèk bracket a kare notasyon ak yon nonb, ou ka Ale nan yon eleman espesifik nan etalaj la nan konstan tan, gwo O nan yon sèl, se konsa pale. Men te gen kèk enkonvenyans. Ki sa ki yon etalaj pa fè trè fasil? Ki sa ki nan li pa bon nan? ELÈV: [fèbl]. Oratè 1: Ki sa ki nan sa? ELÈV: [fèbl]. Oratè 1: Ogmante nan gwosè. Se konsa, enkonvenyans yo nan etalaj la yo se jisteman opoze a nan sa ki upsides yo. Se konsa yonn nan enkonvenyans yo se ke li nan yon gwosè fiks yo. Se konsa, ou pa ka vrèman grandi li. Ou ka aloue yon moso pi gwo nan memwa, ak lè sa a deplase eleman yo fin vye granmoun nan etalaj la nouvo. Lè sa a, gratis etalaj la fin vye granmoun, pou egzanp, lè l sèvi avèk malok oswa yon menm jan an fonksyon rele realloc, ki reafèkt memwa. Realloc, kòm yon sou kote, ap eseye ba ou memwa sa a, se akote etalaj la ke ou te deja genyen. Men, li ta ka deplase bagay sa yo alantou tout ansanm. Men, nan ti bout tan, sa a, se chè, dwa? Paske si ou gen yon ti moso nan memwa nan sa a gwosè, men ou reyèlman vle yon sèl sa a gwosè, epi ou vle prezève eleman yo orijinal la, ou gen apeprè yon lineyè kopye tan pwosesis ki bezwen rive soti nan fin vye granmoun etalaj nan nouvo. Men, reyalite a ap mande opere nan sistèm ankò e ankò ak ankò pou fragman gwo nan memwa ka kòmanse yo ka koute ou kèk tan kòm byen. Se konsa, li tou de yon benediksyon ak yon madichon nan degize, lefèt ke sa yo ranje yo se nan gwosè fiks yo. Men, si nou prezante olye yon bagay tankou sa a, ki nou rele yon lye lis, nou jwenn yon upsides ak kèk yon enkonvenyans kèk isit la tou. Se konsa, yon lis ki lye se senpleman yon done estrikti te fè leve nan C strukt nan sa a ka, kote yon struct, sonje, se jis yon veso pou youn oswa plis espesifik kalite varyab. Nan ka sa a, ki sa ki fè kalite done parèt yo dwe andedan nan struct a ki dènye fwa nou te rele yon ne? Chak kote sa yo rektang se yon ne. Epitou, chak nan rektang yo ki pi piti andedan nan li se yon kalite done. Ki kalite t 'nou di yo te nan Lendi? Yeah? ELÈV: [fèbl]. Oratè 1: A varyab ak konsèy yon, oswa plis espesyalman, yon Int, pou n, ak yon konsèy nan pati anba a. Tou de nan moun ki rive yo dwe 32 Bits, nan omwen sou yon òdinatè tankou sa a CS50 Aparèy, ak pou yo ap trase egalman nan gwosè. Se konsa, sa yo lè l sèvi avèk konsèy la menm si pou aparamman? Poukisa ajoute sa a flèch kounye a lè ranje yo te se konsa bèl ak pwòp ak senp? Ki sa ki konsèy la ap fè pou nou nan chak nan sa yo nœuds? ELÈV: [fèbl]. Oratè 1: Egzakteman. Li nan di ou kote youn nan pwochen se. Se konsa, mwen sòt de sèvi ak analoji a nan lè l sèvi avèk yon moso fil sòt nan fil sa yo nœuds yo ansanm. Epi sa a, ekzakteman ki sa nou ap fè ak endikasyon paske chak nan sa yo fragman nan memwa pouvwa oswa pa pouvwa gen ki toupre yo, li tounen nan do nan do andedan nan RAM, paske chak fwa ou rele malok di, ban m 'ase bytes pou yon ne nouvo, li ka fè isit la oswa li ta kapab isit la. Li ta ka isit la. Li ta ka isit la. Ou jis pa konnen. Men, lè l sèvi avèk endikasyon nan adrès ki nan sa yo nœuds, ou kapab stitched yo ansanm nan yon fason ki sanble vizyèlman tankou yon lis menm si bagay sa yo tout pwopaje soti nan tout yon sèl ou a oswa de ou oswa jigokte kat ou nan RAM andedan nan pwòp òdinatè ou. Se konsa, anba kote an, Lè sa a, nan yon lis ki lye a se ki sa? Ki sa ki nan yon pri nou ap aparamman peye? ELÈV: [fèbl]. Oratè 1: plis espas, dwa? Nou te, nan ka sa a, double kantite lajan an nan espas paske nou te ale soti nan 32 Bits pou chak ne, pou chak Int, se konsa kounye a 64 Bits paske nou gen kenbe otou yon konsèy tou. Ou jwenn plis efikasite si struct ou se pi gwo pase bagay sa a ki senp. Si ou gen aktyèlman yon elèv andedan nan ki se yon koup nan strings pou Non ak kay, petèt yon ID nimewo, petèt kèk jaden lòt tout ansanm. Se konsa, si ou gen yon gwo struct ase, lè sa a petèt pri pou peye pou konsèy a se pa tankou yon kontra gwo. Sa a se yon ti jan nan yon ka kwen nan ki nou ap estoke tankou yon senp primitif andedan nan lis la lye. Men, pwen an se menm bagay la. Ou ap definitivman depanse plis memwa, men w ap vin fleksiblite. Paske kounye a si mwen vle ajoute yon eleman nan kòmansman an nan lis sa a, Mwen gen asiyen yon ne nouvo. Apre sa, mwen gen jis mete ajou moun flèch yon jan kanmenm pa jis k ap deplase kèk endikasyon alantou. Si m 'vle mete yon bagay nan la presegondè nan lis la, mwen pa gen pouse tout moun sou kote tankou nou te fè nan sot pase yo semèn 'ak volontè nou yo ki reprezante yon etalaj. Mwen ka jis asiyen yon ne ak nouvo Lè sa a, jis pwen flèch yo nan diferan direksyon paske li fè sa ki pa gen yo rete nan aktyèl memwa yon liy vre tankou mwen te trase l 'isit la sou ekran an. Lè sa a, alafen, si ou vle insert yon bagay nan fen nan lis la, li nan menm vin pi fasil. Sa a se sòt de notasyon abitrè, men konsèy 34 an, pran yon devine. Ki sa ki se valè a nan konsèy li yo ki pi gen anpil chans sòt trase nan tankou yon fin vye granmoun antèn lekòl la? ELÈV: [fèbl]. Oratè 1: Li pwobableman nil. Ak tout bon ki se youn otè a reprezantasyon nan nil. Epi li nil paske ou absoliman bezwen konnen ki kote nan fen yon lye lis la se pou ou kenbe sa yo ak swiv epi suiv sa yo flèch nan kèk valè fatra. Se konsa, nil ap siyifi ke gen nan pa gen plis nœuds a dwat a nimewo 34, nan ka sa a. Se konsa, nou pwopoze ke nou kapab aplike sa a ne nan kòd. Epi nou te wè sa a kalite nan sentaks anvan. Tipedèf jis defini yon nouvo tip pou nou, ba nou yon synonym tankou fisèl te pou * Char. Nan ka sa a, li la pral bay nou notasyon steno pou ke ne struct ka olye jis dwe ekri kòm ne, ki se yon cleaner anpil. Li se yon anpil mwens sil. Anndan nan yon ne se aparamman yon Int rele n, ak Lè sa a yon ne struct * ki vle di ekzakteman ki sa nou te vle a flèch vle di, yon konsèy nan yon lòt ne nan egzak menm kalite done. Apre sa, mwen pwopoze ke nou te kapab aplike yon fonksyon rechèch tankou sa a, ki nan premye gade ta ka sanble yon konplèks ti kras. Men, kite a wè li nan yon kontèks. Kite m 'janbe lòt bò nan aparèy la isit la. Kite m 'louvri moute yon dosye rele lis zewo dot h. Men, ke se sèlman gen definisyon an nou jis te wè yon ti moman de sa pou sa a done di ki kalite rele yon ne. Se konsa, nou te mete ke nan yon dosye h dot. Men, kòm yon sou kote, menm si sa a pwogram ke w ap sou yo wè se pa tout sa ki konplèks, li la tout bon konvansyon lè li ap ekri yon pwogram nan mete bagay sa yo tankou kalite done, rale konstan pafwa, andedan nan ou dosye header e li pa nesesèman nan dosye C ou a, sètènman lè ou pwogram jwenn pi gwo ak pi gwo, se konsa ke ou konnen ki kote yo gade tou de pou dokiman nan kèk ka, oswa pou Basics yo tankou sa a, definisyon nan kèk kalite. Si m 'koulye a louvri moute lis zewo dot c, remake yon bagay kèk. Li gen ladan l yon dosye header kèk, ki pi nan ki nou te wè anvan. Li gen ladan l dosye header pwòp li yo. Men, kòm yon sou kote, poukisa sa a, se doub quotes isit la, kòm opoze a ang lan parantèz sou liy lan ki Mwen te make a? ELÈV: [fèbl]. Oratè 1: Yeah se konsa li a yon dosye lokal yo. Se konsa, si li nan yon dosye lokal yo nan pwòp ou isit la sou liy 15, pou egzanp, ou sèvi ak quotes yo doub olye nan parantèz yo Incline. Koulye a, sa a se kalite ki enteresan. Remake mwen te deklare yon mondyal varyab nan pwogram sa a sou liy 18 rele premye, lide a ke yo te sa a se pral gen yon konsèy ak pi gran an ne nan lis lye m 'yo, mwen te initialisé li nan nil, paske mwen te ki pa afekte yon nenpòt aktyèl nœuds jis ankò. Se konsa, sa a reprezante, pictorially, ki sa nou wè yon ti moman de sa nan foto a kòm ki konsèy sou byen lwen nan kite bò men yo. Se konsa, kounye a, ki konsèy pa gen yon flèch. Li olye se jis nil. Men, li reprezante sa ki pral la adrès aktyèl la nan premye ne nan lis sa a. Se konsa, mwen te aplike li se yon mondyal paske, kòm ou pral wè yo, tout sa a pwogram nan lavi se aplike yon lis lye pou mwen. Koulye a, mwen te gen yon prototip kèk isit la. Mwen deside aplike karakteristik tankou sipresyon, ensèsyon, chèche, ak parcourt - dènye ti mache nan jis ke yo te toupatou nan nan lis, enprime soti eleman li yo. Epi, koulye a isit la nan woutin prensipal m 'yo. Men, nou pa pral pase twòp tan sou sa yo depi sa a se sòt de, èspere ke fin vye granmoun chapo pa kounye a. Mwen pral fè bagay sa yo, pandan y ap itilizatè a kowopere. Se konsa, yon sèl, mwen pral ekri ak lèt ​​detache sa a meni. Apre sa, mwen te fòma li kòm propr jan mwen te kapab. Si itilizatè a kalite nan yon sèl, sa vle di yo vle efase yon bagay. Si itilizatè a kalite nan de, sa vle di yo vle mete yon bagay. Ak pou fè. Mwen pral Lè sa a, pouse Lè sa a, pou yon lòd. Lè sa a, mwen pral sèvi ak GetInt. Se konsa, sa a se yon menuing vrèman senp koòdone yo kote ou jis gen nan tape yon nimewo kat nan yon sèl nan tout sa yo kòmandman. Epi, koulye a mwen gen yon bèl switch pwòp deklarasyon ki di ke nan ale nan chanje sou tou sa itilizatè a tape pous Men, si yo tape yon sèl, mwen pral rele efase epi kase. Si yo tape de, mwen pral rele insert epi kase. Epi, koulye a notifikasyon mwen te mete chak nan sa yo sou liy lan menm. Sa a se jis yon desizyon stylistic. Tipikman nou te wè yon bagay tankou sa a. Men, mwen jis deside, franchman, pwogram mwen gade plis lizib paske li te sèlman kat ka jis mete l tankou sa a. Totalman lejitim pou sèvi ak style. Men, mwen pral fè sa toutotan la itilizatè pa te tape zewo, ki mwen deside pral vle di yo vle kite fimen. Se konsa, kounye a remake ki sa mwen se pral fè isit la. Mwen pral libere lis la aparamman. Men, plis sou sa nan jis moman sa a. Ann premye kouri pwogram sa a. Se konsa, kite m 'fè yon tèminal pi gwo fenèt, dot koupe lis 0. Mwen pral ale pi devan epi insert pa de sezisman, yon kantite tankou 50, epi kounye a ou pral wè lis la se kounye a 50. Ak tèks mwen jis defiled moute yon ti jan. Se konsa, kounye a remake lis la gen nimewo a 50. Se pou yo fè yon lòt insert pa pran de. Se pou yo tape nan kantite tankou yon sèl. Lis se kounye a yon sèl, ki te swiv pa 50. Se konsa, sa a se jis yon reprezantasyon textuelle nan lis la. Li kite yo mete yon sèl plis kantite tankou nimewo a 42, ki se èspere ke ale nan fini nan mitan an, paske pwogram sa a nan kalite patikilye li eleman jan li foure yo. Se konsa, gen nou genyen li. Super pwogram senp ki te kapab absoliman te itilize yon etalaj, men mwen rive yo dwe lè l sèvi avèk yon lis lye jis pou mwen kapab dynamique grandi ak retresi li. Se konsa, kite a pran yon gade pou rechèch, si mwen kouri lòd twa, mwen vle fè rechèch pou, di, nimewo a 43. E pa gen anyen te aparamman te jwenn, paske mwen te tounen pa gen okenn repons. Se konsa, kite a fè sa ankò. Rechèch la. Rechèch Ann pou 50, ou pito rechèch pou 42, ki te gen yon bèl ti kras sans sibtil. Apre sa, mwen te jwenn siyifikasyon an nan lavi a. Nimewo 42, si ou pa konnen referans a, Google l '. Tout dwa. Se konsa, sa ki te nan pwogram sa a fè pou mwen? Li nan jis pèmèt m 'nan insert konsa byen lwen ak rechèch pou eleman. Se pou yo vit pou pi devan, Lè sa a, nan ki fonksyon nou regarda nan nan Lendi kòm yon kol. Se konsa, fonksyon sa a, mwen fè reklamasyon, rechèch pou yon eleman nan lis la pa premye yon sèl, sa ki pouse itilizatè a ak Lè sa a rele GetInt jwenn yon Int aktyèl ke ou vle pou fè rechèch pou. Lè sa a, remake sa a. Mwen pral kreye yon varyab pou yon ti tan nan liy 188 rele konsèy - Ptr - te kapab rele l 'anyen. Lè li nan yon konsèy nan yon ne paske m 'te di ne * la. Ak mwen se inisyalizin li nan dwe egal a premye pou m 'efektivman gen mwen dwèt, se konsa pale, sou anpil la premye eleman nan lis la. Se konsa, si men dwat mwen an isit la se ptr mwen se montre nan menm bagay la ki premye ap montre a. Se konsa, kounye a li tounen nan Kòd, sa k ap pase pwochen - sa a se yon paradigm komen lè iteration sou yon estrikti tankou yon lye lis la. Mwen pral fè bagay sa yo pandan y ap konsèy se pa egal a nil Se konsa, pandan y ap dwèt mwen pa montre nan kèk nil valè, si konsèy flèch n egal n. Nou pral remake premye ki n se sa ki nan itilizatè tape nan GetInts pou chak rele isit la. Men, konsèy flèch n vle di ki sa? Oke, si nou tounen nan foto a isit la, si mwen gen yon dwèt montre nan ki ne premye ki gen nèf la, flèch esansyèlman vle di ale nan ki ne ak pwan valè a nan kote n, nan ka sa a, jaden an done rele n. Kòm yon sou kote - epi nou te wè sa a yon koup nan semèn de sa lè yon moun mande - sa a sentaks se nouvo, men li pa fè sa ban nou pouvwa pou nou pa t 'te deja genyen. Ki sa ki te fraz sa a ekivalan a lè l sèvi avèk dot notasyon ak zetwal yon koup nan semèn de sa lè nou kale tounen kouch sa a yon ti jan prematireman? ELÈV: [fèbl]. Oratè 1: Egzakteman, li te zetwal, ak Lè sa a, li te zetwal dot n, ak parantèz isit la, ki sanble, franchman, mwen panse ke yon anpil plis skre li. Men, zetwal konsèy, tankou toujou, vle di ale la. Ak yon lòt fwa w ap gen, ki sa done jaden ou vle gen aksè a? Byen ou itilize notasyon a dot jwenn aksè nan yon strukt done jaden, epi mwen espesyalman vle n. Franchman, mwen ta diskite sa a se jis pi rèd li. Li nan pi rèd sonje ki kote parantèz yo ale a, zetwal yo ak tout sa. Se konsa, mond lan te adopte kèk Massachusetts Institute of Technology sik, se konsa pale. Jis yon fason sexy nan li di yo: sa a se ekivalan, ak petèt plis entwisyon. Si konsèy se vre yon konsèy, nan vle di notasyon flèch ale la epi jwenn jaden an nan ka sa a yo rele n. Se konsa, si mwen jwenn li, remake sa m 'fè. Mwen tou senpleman enprime soti, mwen jwenn pousan mwen, rakorde nan valè a pou ke Int. Mwen rele dòmi pou yon dezyèm jis kalite de bagay sa yo pran yon poz sou ekran an bay itilizatè a yon dezyèm yo absòbe sa ki jis rive. Lè sa a, mwen kraze. Sinon, sa m 'fè? Mwen mete konsèy egal flèch konsèy kap vini an. Se konsa, jis yo dwe klè, sa vle di ale la, lè l sèvi avèk notasyon fin vye granmoun-lekòl mwen an. Se konsa, sa a jis vle di pou yo ale nan tou sa w ap lonje dwèt nan, ki nan anpil nan ka premye se mwen montre nan struct a ak nèf nan li. Se konsa, mwen te ale a. Lè sa a, notasyon an dot vle di, jwenn valè a nan pwochen an. Men, valè a, menm si li nan trase kòm yon etwat, se jis yon nimewo. Li se yon adrès nimerik. Se konsa, liy sa a youn nan Kòd, si wi ou non ekri nan Liv la tankou sa a, plis skre la fason sa a, oswa tankou sa a, yon ti kras plis nan fason entwisyon, jis vle di deplase men m ' soti nan ne an premye nan yon sèl kap vini an, ak Lè sa a kap vini yo yon sèl la, ak Lè sa a, nan pwochen yon sèl, ak pou fè. Se konsa, nou pa pral rete sou lòt la en nan insert ak efase ak parcourt, de nan premye nan ki se jistis enplike nan sa. Apre sa, mwen panse ke li trè fasil yo ka resevwa pèdi lè fè li vèbalman. Men, sa nou kapab fè isit la se eseye detèmine kijan pi byen fè sa a vizyèlman. Paske mwen ta pwopoze ke si nou vle insert eleman nan sa a ki deja egziste lis, ki gen senk eleman - 9, 17, 22, 26, ak 33 - si mwen te ale nan aplike sa a nan Kòd, mwen bezwen konsidere ki jan yo ale sou fè sa. Apre sa, mwen ta pwopoze pran mezi ti bebe kijan, nan ka sa a mwen vle di, ki sa yo senaryo ki posib ke nou ka rankontre an jeneral? Lè mete ann aplikasyon insert pou yon lye lis, sa a jis k ap pase yo yon egzanp espesifik nan gwosè senk. Oke, si ou vle insert yon nimewo, renmen di nimewo nan yon sèl, ak kenbe Ranje lòd, kote evidamman fè nimewo nan yon sèl bezwen ale nan egzanp sa a espesifik yo? Tankou nan kòmansman an. Men, sa ki nan enteresan gen ki si ou vle insert yon sèl nan sa a lis, ki sa ki konsèy espesyal bezwen yo dwe mete ajou aparamman? Premye. Se konsa, mwen ta diskite, sa a se ka a premye ke nou ta ka vle konsidere, yon senaryo ki enplike yo mete nan nan konmansman an nan lis la. Se pou yo rache koupe petèt yon kòm fasil oswa menm pi fasil ka, relativman pale. Sipoze mwen vle insert la nimewo 35 nan Ranje lòd. Li evidamman ki dwe sou la. Se konsa, sa konsèy evidamman ki pral gen yo dwe mete ajou nan ki senaryo? Konsèy 34 an vin pa nil men adrès la nan struct la ki gen nimewo a 35. Se konsa, sa a, se ka de. Se konsa, deja, mwen se sòt de kantifye konbyen travay mwen gen fè isit la. E finalman, ka a nan mitan evidan se tout bon, nan mitan an, si mwen vle insert yon bagay tankou 23, di ke ale ant 23 an ak 26 an, men kounye a bagay sa yo jwenn yon ti kras pi plis patisipe paske sa endikasyon bezwen chanje? Se konsa, 22 evidamman bezwen yo dwe chanje paske li pa ka lonje dwèt sou 26 ankò. Li bezwen lonje dwèt sou ne la nouvo ki Mwen pral oblije asiyen lè w rele malok oswa ekivalan kèk. Men, lè sa a mwen bezwen tou ki ne nouvo, 23 nan ka sa a, yo gen konsèy li yo montre nan ki moun? 26. Apre sa, k ap pase yo dwe genyen yon lòd operasyon isit la. Paske, si mwen fè sa a tankou moun fou, ak mwen pou kòmanse egzanp nan konmansman an nan lis la, ak objektif mwen an se insert 23. Apre sa, mwen tcheke, li fè pati isit la, tou pre nèf? No li fè pati isit la, akote 17? No Èske li fè pati isit la kap vini yo a 22? Wi. Koulye a, si mwen se moun fou isit la, epi yo pa panse sa a nan, mwen ta ka asiyen ne nouvo mwen an pou 23. Mwen ta ka mete konsèy la soti nan ne a rele 22, montre li nan ne a nouvo. Lè sa a, sa m 'genyen aktyalizasyon konsèy ne nan nouvo nan ta dwe ye? ELÈV: [fèbl]. Oratè 1: Egzakteman. Montre nan la 26. Men, dammit si mwen pa t 'deja aktyalizasyon Konsèy 22 a nan pwen nan nèg sa a, ak koulye a, mwen gen timoun ki san papa, rès la nan lis la, se konsa pale. Se konsa, lòd operasyon isit la a pwal enpòtan. Pou fè sa te kapab mwen vòlò, di, sis volontè yo. Li kite yo wè si nou pa ka fè sa vizyèlman olye pou yo kòd-ki gen bon konprann. Epi nou gen kèk estrès bèl voye boul pou ou jodi a. OK, ki jan sou yonn, de,, nan la tounen - sou fen a la. twa, kat, tou de nan nou mesye sou fen a. Men, senk, sis. Asire w. Senk ak sis. Tout dwa epi n ap vin ou mesye pwochen fwa. Tout dwa, vini sou yo. Tout dwa, depi w ap moute isit la an premye, ou ta renmen yo dwe youn nan malabiyman nan Google Glass isit la? Tout dwa, se konsa, OK, vè, dosye yon videyo. OK, w ap bon yo ale. Tout dwa, kidonk si w mesye ka vin sou isit la, mwen pare pou nou an avanse kèk nimewo. Tout dwa, vini sou plis pase isit la. Men, poukisa ou pa ale yon ti kras plis ki fason. Li kite yo wè la a, sa ki nan non ou, ak glas la Google? ELÈV: Ben. Oratè 1: Ben? OK, Ben, ou pral premye, literalman. Se konsa, nou ap ale nan voye ba ou nan fen a nan etap la. Tout dwa, ak non ou an? ELÈV: Jason. Oratè 1: Jason, OK ou pral gen nimewo nèf. Se konsa, si ou vle swiv Ben ki fason. ELÈV: Jill. Oratè 1: Jill, w ap ale nan dwe 17, ki si mwen ta fè sa plis intelijans, mwen ta gen te kòmanse nan fen a lòt. Ou ale ki fason. 22. Epi ou yo ye? ELÈV: Mari. Oratè 1: Mari, ou pral 22. Men, non ou se? ELÈV: Chris. Oratè 1: Chris, ou pral 26. Lè sa a, anfen. ELÈV: Diana. Oratè 1: Diana, ou pral 34. Se konsa, ou vini sou plis pase isit la. Tout dwa, se konsa pafè Ranje lòd deja. Li kite yo ale pi devan epi fè sa pou nou ka vrèman - Ben w ap jis kalite kap soti nan okenn kote la. OK, se konsa kite a ale pi devan epi dekri sa a lè l sèvi avèk bra yo, anpil tankou mwen te, egzakteman, sa k ap pase sou. Se konsa, ale pi devan epi bay tèt nou yon pye oswa de ant nou. Men, ale pi devan epi pwen ak yon sèl men Nenpòt moun ki ou ta dwe montre nan ki baze sou sa a. Epi si w ap nil jis pwen dwat desann nan etaj la. OK, se konsa bon. Se konsa, kounye a nou gen yon lis lye, ak kite m ' pwopoze ke mwen pral jwe wòl Ptr, se konsa mwen pa pral deranje pote sa a alantou. Lè sa a, - yon moun sòt konvansyon - ou ka rele sa a nenpòt sa ou vle - konsèy predesesè, prèd konsèy - li nan jis tinon a nou te ba nan Kòd echantiyon nou yo men gòch mwen. Lòt men an ki yo pral kenbe tras de ki moun ki ki moun ki nan la apre senaryo. Se konsa, ta kwè, an premye, mwen vle rache sou ki egzanp premye nan yo mete, di 20, nan lis la. Se konsa, mwen pral bezwen yon moun enkòpore nimewo a 20 pou nou. Se konsa, mwen bezwen yon moun malok soti nan odyans lan. Vini non sou yo. Ki sa ki nan non ou? ELÈV: Brian. Oratè 1: Brian yo, tout dwa, kidonk, ou va ne a ki gen 20. Tout dwa, vini sou plis pase isit la. Men, evidamman, kote Brian apatni? Se konsa, nan mitan an nan - aktyèlman, rete tann yon minit. Nou ap fè sa a parèt nan lòd. Nou ap fè sa a yon anpil pi rèd pase sa li bezwen yo dwe an premye. OK, nou pral gratis Brian ak realloc Brian kòm senk. OK, se konsa, koulye a nou vle insert Brian kòm senk. Se konsa, vini sou plis pase isit la akote Ben sèlman pou moman yon. Epi ou ka prezimableman di kote istwa sa a ki pral. Men, kite a reflechi byen sou lòd operasyon. Epi li jisteman sa a vizyèl ki nan ale nan liy moute ak sa Kòd egzanp lan. Se konsa, isit la mwen te ptr montre okòmansman pa nan Ben, se pou chak, men nan tou sa apresye li gen la, ki nan ka sa a se - sa ki nan non ou ankò? ELÈV: Jason. Oratè 1: Jason, se konsa tou de Ben ak mwen yo montre nan Jason nan moman sa a. Se konsa, koulye a, mwen gen detèmine, kote Brian apatni? Se konsa, bagay la sèlman mwen gen aksè nan kounye a se n l 'done atik. Se konsa, mwen pral tcheke, se Brian mwens pase Jason? Repons lan se vre. Se konsa, sa kounye a bezwen yo rive, nan lòd ki kòrèk? Mwen bezwen mete ajou konbyen endikasyon nan total ki nan istwa sa a? Ki kote men m 'se toujou montre nan Jason, ak men ou - si ou vle mete men ou tankou, sòt de, mwen pa konnen, yon mak kesyon. OK, bon. Tout dwa, kidonk, ou gen yon kandida kèk. Swa Ben oswa mwen oswa Brian oswa Jason oswa tout lòt moun yo, ki endikasyon bezwen chanje? Konbyen nan total manm? OK, se konsa de. Konsèy mwen pa reyèlman gen pwoblèm ankò paske mwen se jis yon ti tan. Se konsa, li mesye sa yo de, prezimableman, tou de Ben ak Brian. Se konsa, kite m 'pwopoze ke nou mete Ben, depi li se an premye. Eleman an premye nan lis sa a se kounye a yo pral Brian. Se konsa, Ben pwen nan Brian. OK, kounye a ki sa? Kilès ki ka atrape pwente nan ki moun? ELÈV: [fèbl]. Oratè 1: OK konsa Brian gen nan pwen nan Jason. Men, m 'pèdi tras nan ki konsèy? Mwen konnen ki kote Jason se? ELÈV: [fèbl]. Oratè 1: m 'fè, depi mwen se konsèy la yon ti tan. Men, prezimableman, mwen pa te chanje nan pwen nan ne a nouvo. Se konsa, nou ka senpleman gen Brian pwen nan moun ki mwen montre nan. Men, nou ap fè. Se konsa, ka yon sèl, ensèsyon nan la kòmanse nan lis la. Vwala te gen de etap kle. Youn, nou gen aktyalizasyon Ben, ak Lè sa a, nou menm tou nou gen mizajou nan Brian. Lè sa a, mwen pa gen bezwen deranje traipsing nan rès la nan la lis, paske nou deja jwenn li kote, paske li ki te fè pati nan rete nan eleman a an premye. Tout dwa, se konsa trè senp. An reyalite, santi l tankou nou ap prèske fè sa a twò konplike. Se konsa, kite a kounye a rache koupe nan fen nan lis la, epi wè ki kote konpleksite nan kòmanse. Se konsa, si koulye a, mwen alok soti nan odyans lan. Nenpòt moun ki vle jwe 55? Tout dwa, mwen te wè men ou an premye. Vini non sou yo. Yeah. Ki sa ki nan non ou? ELÈV: [fèbl]. Oratè 1: Habata. OK, vini sou yo. Ou pral nimewo a 55. Se konsa, ou, nan kou, fè pati nan fen nan lis la. Se konsa, kite a reparèt simulation la avè m ' yo te ptr a sèlman pou moman yon. Se konsa, mwen premye ale nan pwen nan tou sa Ben a montre nan. Nou ap tou de montre kounye a nan Brian. Se konsa, 55 se pa mwens pase senk. Se konsa, mwen pral mete ajou tèt mwen pa montre konsèy pwochen Brian a, ki moun ki kounye a se nan kou Jason. 55 se pa mwens pase nèf, se konsa Mwen pral mete ajou ptr. Mwen pral mete ajou ptr. Mwen pral mete ajou ptr Mwen pral mete ajou ptr. Men, mwen pral - hmm, sa ki nan non ou ankò? ELÈV: Diana. Oratè 1: Diana ap montre, nan kou, nan nil ak men gòch li. Se konsa, kote fè Habata aktyèlman fè pati byen klè? Sou bò goch la, isit la. Se konsa, kouman mwen konnen yo mete l 'Isit la Mwen panse mwen te vise yo. Paske sa ki ptr atizay moman sa a nan tan? Nil. Se konsa, menm si, vizyèlman, nou ka evidamman wè tout moun sa yo mesye isit la sou etap yo. Mwen pa te kenbe tras nan anvan yo nan moun ki nan lis la. Mwen pa gen yon dwèt montre yo, nan ka sa a, ki kantite ne 34. Se konsa, kite a aktyèlman kòmanse sa a sou. Se konsa, koulye a, mwen aktyèlman bezwen yon dezyèm varyab lokal yo. Lè sa a se ki sa ou pral wè nan a reyèl echantiyon C Kòd, kote kòm m 'ale, lè m 'mete men dwat mwen an nan pwen Jason, kidonk kite Brian dèyè, mwen pi bon kòmanse lè l sèvi avèk men gòch mwen an mizajou nan kote mwen te, se konsa ke jan mwen ale nan lis sa a - plis malabiyman pase m gen entansyon kounye a isit la vizyèlman - Mwen pral pou li ale nan nan fen nan lis la. Sa a men se toujou nil, ki se trè initil, lòt pase yo endike Mwen se klèman nan fen lis la, Men, koulye a omwen mwen gen sa a konsèy predesesè montre isit la, se konsa Koulye a, kisa men ak sa ki endikasyon bezwen yo dwe mete ajou? Ki moun men ou vle rkonfigurasyon an premye? ELÈV: [fèbl]. Oratè 1: OK, se konsa a Diana. Ki kote ou vle nan pwen Bò gòch konsèy Diana a nan? Nan 55, prezimableman, se konsa ke nou te antre a. Ak ki kote yo ta dwe 55 konsèy 'al jwenn? Desann, sa ki reprezante nil. Men, men m ', nan pwen sa a, pa fè sa gen pwoblèm paske yo te jis varyab yon ti tan. Se konsa, kounye a nou ap fè. Se konsa, konpleksite nan plis gen - ak li pa ki difisil yo aplike, men nou bezwen yon varyab segondè yo fè asire w ke mwen anvan m 'deplase dwat mwen men, mwen mete valè a nan gòch mwen men, prèd konsèy nan ka sa a, se konsa ke mwen gen yon konsèy fin kenbe tras nan kote mwen te ye a. Koulye a, kòm yon sou kote, si w ap panse sa a nan, sa a santi l tankou li nan yon ti kras anmèdan gen kenbe swiv sa a men gòch. Ki sa ki ta yon lòt solisyon a pwoblèm sa a yo te? Si ou te rive nan Restriktirasyon done yo estrikti nou ap pale nan kounye a? Si sa a kalite jis nan santi l yon ti kras anmèdan genyen, renmen, de pwent ale atravè tout lis la, ki moun ki lòt moun kapab yo te, nan yon mond ideyal, konsève enfòmasyon ke nou bezwen? Yeah? ELÈV: [fèbl]. Oratè 1: Egzakteman. Dwa Se konsa, gen la aktyèlman yon enteresan jèm nan yon lide. Lè sa a lide nan yon konsèy anvan-an, montre nan eleman nan anvan yo. E si mwen jis incorporée ki andedan nan lis nan tèt li? Epi li pral fè difisil visualized sa a san yo pa tout papye a tonbe sou planche-a. Men, si ke mesye sa yo itilize tou de yo nan men yo gen yon anvan yo konsèy, ak yon konsèy kap vini yo, kidonk mete ann aplikasyon sa nou pral rele yon doubl lye lis la. Sa ta pèmèt mwen sòt de remonte, pi plis fasil san yo pa m ', la pwogramè, li te gen kenbe swiv manyèlman - se vre wi: manyèlman - nan kote mwen te deja nan lis la. Se konsa, nou pa pral fè sa. Nou pwal kenbe li senp paske se ale nan vin nan yon pri, de fwa tankou anpil espas pou endikasyon yo, si ou vle yon yon sèl dezyèm fwa. Men, sa a tout bon yon komen done estrikti li te ye kòm yon doubl lye lis la. Se pou yo fè egzanp final la isit la, li mete mesye sa yo soti nan mizè yo. Se konsa, malok 20. Vini non sou moute soti nan ale nan la. Tout dwa, sa ki nan non ou? ELÈV: [fèbl]. Oratè 1: Padon? ELÈV: [fèbl]. Oratè 1: Demeron? OK vin sou yo. Ou va gen 20. Ou evidamman yo ale nan fè pati ant 17 ak 22. Se konsa, kite m 'aprann leson m' yo. Mwen pral kòmanse konsèy montre nan Brian. Men, mwen pral gen men gòch mwen sèlman Mizajou Brian jan mwen deplase nan Jason, tcheke fè 20 mwens pase nèf? No A se 20 mwens pase 17? No A se 20 mwens pase 22? Wi. Se konsa, endikasyon ki sa ou oswa men w bezwen chanje kote yo ap montre kounye a? Se konsa, nou ka fè 17 montre nan 20. Se konsa, sa a, se amann. Ki kote nou vle rive nan pwen konsèy ou an kounye a? Nan 22. Epi nou konnen ki kote 22 se, ankò mèsi pou yon ti tan konsèy m 'yo. Se konsa, nou ap OK la. Se konsa, paske sa a depo pou yon ti tan Mwen te kenbe tras nan kote tout moun se. Epi, koulye a ou ka wè ale nan kote ou genyen, epi kounye a nou bezwen 1, 2, 3, 4, 5, 6, 7, 8, 9 voye boul estrès, ak yon wonn nan aplodisman pou mesye sa yo, si nou te kapab. Joliman fè. [Aplodisman] Oratè 1: Tout dwa. Epi ou ka kenbe moso yo papye kòm souvnir. Tout dwa, se konsa, kwè m 'li nan yon anpil pi fasil yo mache nan ke ak moun pase sa li se avèk kòd vrè. Men, sa ki w ap jwenn nan jis moman sa yon kounye a, se ke menm - oh, di ou mèsi. Mèsi poutèt ou - se ke ou ap jwenn ki done yo menm estrikti, yon lis lye, ka aktyèlman dwe itilize kòm yon blòk bilding menm plis done sofistike estrikti. Ak reyalize twò tèm nan isit la se ke nou te absoliman prezante plis konpleksite nan aplikasyon an sa a algorithm. Ensèsyon, epi si nou mache ale nan tout li, sipresyon ak rechèch, se yon ti kras pi konplike pase sa li te la avèk yon etalaj. Men, nou jwenn kèk dinamik. Nou jwenn yon estrikti ki done ki ede adaptasyon. Men, ankò, nou peye yon pri nan gen kèk plis konpleksite, tou de nan mete ann aplikasyon li. Men, nou ap bay moute o aza aksè. Men, yo dwe onèt, gen nan pa gen kèk bèl netwaye glise mwen ka ba ou ki di isit la se poukisa yon lis ki lye se pi bon pase yon etalaj. Epi kite li nan sa. Paske tèm nan rekurant kounye a, menm plis konsa nan semèn kap vini, se ki gen nan pa nesesèman yon repons ki kòrèk. Sa a se rezon sa a genyen aks apa nan konsepsyon pou kouche pwoblèm. Li pral trè kontèks sansib si ou vle sèvi ak done sa yo estrikti oswa yon sèl, epi li pral depann sou sa ki enpòtan ba ou an tèm resous ak konpleksite. Men, kite m 'pwopoze ke done yo ideyal estrikti, grail a apa pou Bondye, ta dwe yon bagay ki lè konstan, endepandaman de ki jan bagay anpil se andedan li, pa li ta dwe etonan si yon done estrikti tounen repons nan konstan tan. Wi. Mo sa a se nan diksyonè gwo ou. Oswa ki pa gen, pawòl sa a se pa vre. Oswa nenpòt pwoblèm ki sa yo la. Oke kite la wè si nou pa kapab omwen pran yon etap nan direksyon sa. Kite m 'pwopoze yon estrikti done nouvo ki kapab itilize pou bagay sa yo diferan, nan ka sa a yo rele yon tab regle. Se konsa, nou ap aktyèlman tounen nan ensidan nan yon etalaj, nan ka sa a, ak yon ti jan abitrèman, mwen te trase sa a regle tab kòm yon etalaj ak sòt de yon ki genyen de dimansyon etalaj - oswa olye li a montre isit la kòm yon de dimansyon etalaj - men sa a se jis yon etalaj de gwosè 26, tankou ke si nou rele tab la etalaj, bracket tab zewo se rektang lan nan tèt la. Table bracket 25 se rektang lan nan pati anba a. Men ki jan mwen ta ka trase yon done estrikti nan ki mwen vle nan magazen moun nan non. Se konsa, pou egzanp, e mwen pa pral trase a tout bagay isit la sou anlè tèt yo, si mwen te gen sa a etalaj, ki mwen kounye a ale nan rele yon tab regle, e sa se ankò kote zewo. Sa a isit la se kote yon sèl, ak pou fè. Mwen reklamasyon ke mwen vle yo sèvi ak done sa yo estrikti, pou dedomajman pou la nan diskisyon, nan magazen non moun nan, Alice ak Bob ak Charlie ak lòt non sa yo. Se konsa, panse a sa a kounye a kòm premye jou nan, di, yon diksyonè avèk anpil mo yo. Yo rive yo dwe non nan egzanp nou an isit la. Lè sa a se tout twò konvnabl, petèt, nan mete ann aplikasyon yon korektè eple, jan nou ta ka pou pwoblèm mete sis. Se konsa, si nou gen yon etalaj de gwosè total 26 se konsa ke sa a se ki kote 25th nan pati anba a, epi mwen reklamasyon ke Alice se pawòl Bondye a an premye nan diksyonè a nan non mwen vle insert nan RAM, nan estrikti sa a done, kote yo ensten di ou ke Alice an Non ta dwe ale nan sa a etalaj? Nou gen 26 opsyon. Ki kote nou vle mete li? Nou vle l 'nan bracket zewo, dwa? A pou Alice, se pou yo rele ki zewo. Ak B pral fè yon sèl, ak C, va gen de. Se konsa, nou ap ale nan ekri Non Alice a moute isit la. Si nou Lè sa a, insert Bob, l ' Non yo ap ale isit la. Charlie pral ale isit la. Ak pou fè desann nan sa a done estrikti. Sa a se yon estrikti done bèl bagay. Poukisa? Oke sa a se tan a kouri nan yo mete non yon moun la nan sa a done estrikti kounye a? Etandone ke sa a se tab aplike, se vre wi:, menm jan yon etalaj. Oke li nan tan konstan. Li nan lòd nan yon sèl. Poukisa? Oke ki jan ou detèmine kote Alice fè pati? Ou gade nan ki lèt nan non li? Premye a. Epi ou ka jwenn gen, si li nan yon fisèl, pa jis gade nan fisèl bracket zewo. Se konsa, pèsonaj la zeroth nan fisèl la. Sa a fasil. Nou te fè sa nan chifreman a semèn plasman de sa. Lè sa a, yon fwa ou konnen ke nan Alice lèt ki se kapital A, nou ka fè soustraksyon sou 65 lane oswa kapital Yon tèt li, ki bay nou zewo. Se konsa, nou kounye a konnen ke Alice fè pati nan kote zewo. Men, bay yon konsèy sa a done estrikti, nan kèk sòt, konbyen tan li pran m 'jwenn kote zewo nan yon etalaj? Jis yon sèl etap, dwa Li lè konstan paske nan aksè nan o aza nou pwopoze te yon karakteristik nan yon etalaj. Se konsa, nan kout, lè n ap kalkile konnen ki sa ki endèks la nan Non Alice a se, ki se, nan ka sa a, se A, oswa kite yo jis rezoud ki a zewo, kote B se yon sèl ak C se de, lè n ap kalkile ki soti se tan konstan. Mwen jis gen gade nan lèt premye l ', lè n ap kalkile konnen ki kote zewo se yon etalaj se tou tan konstan. Se konsa, teknikman sa a, se tankou de etap kounye a. Men, sa a toujou konstan. Se konsa, nou rele ki O gwo nan yon sèl, se konsa nou te eleman Alice nan tablo sa a nan konstan tan. Men, nan kou, mwen te nayif isit la, dwa? E si gen nan yon Arawon nan klas la? Oswa Alicia? Oswa nenpòt lòt non kòmanse avèk A. Ki kote nou pral mete moun sa a, dwa? Mwen vle di, kounye a gen nan sèlman twa moun sou tab la, se konsa petèt nou ta dwe mete Arawon nan kote zewo yon sèl de twa. Dwa, mwen te kapab mete yon isit la. Men, lè sa a, si nou eseye mete David nan lis sa a, kote David ale? Koulye a, sistèm nou an kòmanse kraze desann, dwa? Paske kounye a David fini moute isit la si Arawon se aktyèlman isit la. Se konsa, kounye a ide sa a tout antye ki gen yon pwòp done estrikti ki ba nou parusyon tan konstan se pa konstan tan, paske mwen gen tcheke, o, damnit, yon moun nan deja nan kote Alice an. Kite m 'sonde rès la nan sa a done estrikti, kap chèche yon plas yo mete yon moun tankou non Arawon. Se konsa, sa tou se kòmanse pran lineyè tan. Anplis, si ou kounye a ou vle jwenn la Arawon nan estrikti sa a done, epi ou tcheke, ak non Arawon yo se pa isit la. Idealman, ou ta jis di pou Arawon pa nan estrikti a done. Men, si ou fè kòmanse fè plas pou Arawon kote ki gen ta dwe yon D oswa yon E, nou la a, pi move ka, yo gen yo tcheke estrikti nan done antye, nan ka sa a li devolu nan yon bagay lineyè nan gwosè a nan tab la. Se konsa, tout dwa, mwen pral ranje sa a. Pwoblèm nan isit la se ke mwen te gen 26 eleman sa a nan etalaj. Kite m 'chanje li. Whoops. Kite m 'chanje li pou ke olye ke yo te nan gwosè 26 nan total, remake anba a endèks ki pral chanje nan n mwens 1. Si 26 se klèman twò piti pou 'moun non, paske gen dè milye de non nan mond lan, se pou yo jis fè nan 100 oswa 1,000 oswa 10,000. Se pou yo jis asiyen yon anpil plis espas. Oke ki pa nesesèman diminye pwobabilite ki genyen pou nou pa pral gen de moun ki gen non kòmanse avèk A a, epi se konsa, ou te ale pou yo eseye mete yon non nan zewo kote toujou. Yo ap toujou ale nan kolizyon, ki vle di nou toujou bezwen yon solisyon a mete Alice ak Arawon, li Alicia ak lòt non kòmanse avèk yon lòt kote. Men, ki jan anpil nan yon pwoblèm sa a ye? Ki sa ki nan pwobabilite ki genyen pou ou gen kolizyon nan yon done estrikti tankou sa a? Oke, kite m '- nou ap tounen nan kesyon an isit la. Men, gade nan ki jan nou ta ka rezoud li an premye. Kite m 'rale moute pwopozisyon sa a isit la. Ki sa nou jis dekri se yon algorithm, yon eristik rele lineyè sonde kijan, si ou te eseye mete yon bagay isit la nan sa a done estrikti, ki te rele yon tab regle, ak gen nan pa gen chanm la, ou se vre wi: sonde estrikti nan done tcheke, se sa a ki disponib? Sa a se disponib se sa a ki disponib? Èske sa se disponib? Men, lè li finalman se, ou insert la non ke ou orijinèlman gen entansyon yon lòt kote nan ki kote. Men, nan ka ki pi mal la, plas la sèlman ta kapab anba la anpil nan done yo estrikti, nan fen anpil nan etalaj la. Se konsa, lineyè sonde, nan ka ki pi mal la, devolu nan yon algorithm lineyè kote Arawon, si li k ap pase nan yo pral figire dènye nan estrikti sa a done, li te ka kolizyon ak sa a kote premye, men Lè sa a, fini pa move chans nan fen an anpil. Se konsa, sa a se pa yon konstan tan apa pou Bondye grail pou nou. Apwòch sa a nan yo mete eleman nan yon estrikti done rele yon regle tab pa sanble yo gen konstan tan omwen pa nan ka a an jeneral. Li kapab transfere nan yon bagay lineyè. Se konsa, sa si nou rezoud kolizyon yon ti jan yon lòt jan? Se konsa, isit la nan yon pi plis sofistike apwoche nan sa la toujou rele yon tab regle. Men, pa regle, kòm yon sou kote sa, Mwen vle di se endèks la ki Mwen refere yo bay pi bonè. Regle yon bagay yo ka panse a kòm yon vèb. Se konsa, si ou regle Alice se yon non, yon fonksyon regle, se konsa pale, ta dwe retounen yon nimewo. Nan ka sa a se zewo si li fè pati nan zewo kote, yon sèl si li fè pati nan kote yon sèl, ak pou fè. Se konsa, fonksyon regle mwen konsa byen lwen te gen super senp, sèlman gade nan la premye lèt nan non yon moun. Men, yon fonksyon regle pran kòm D 'kèk moso nan done, yon fisèl, yon Int, kèlkeswa sa. Epi li krache soti tipikman yon nimewo. Lè ladan nimewo se kote ki done eleman ki dwe nan yon estrikti done li te ye isit la kòm yon tab regle. Se konsa, jis entwitif, sa a se yon yon ti kras diferan kontèks. Sa a aktyèlman se refere li a yon egzanp ki enplike anivèsè nesans, kote ka gen kòm anpil 31 jou nan mwa a. Men, sa ki t 'moun sa a deside fè nan evènman an nan yon kolizyon? Context kounye a ke yo te, pa yon kolizyon nan non, men yon kolizyon nan anivèsè nesans, si de moun gen menm jou fèt sou 2nd a nan Oktòb, pou egzanp. ELÈV: [fèbl]. Oratè 1: Yeah, konsa isit la nou gen swe la nan lye li bay lis. Se konsa, li sanble yon ti jan diferan pase nou te mete li pi bonè. Men, nou parèt devan yo gen yon etalaj sou bò men gòch. Sa a yon sèl endèks, paske pa gen patikilye ki rezon. Men, li la toujou yon etalaj. Li nan yon etalaj de pwent. Epitou, chak nan sa yo eleman, yo chak nan sa yo ti sèk oswa bar - koupe a ki reprezante nil - chak nan sa yo endikasyon ki aparamman montre sa estrikti done? Yon lis lye. Se konsa, kounye a nou gen kapasite nan difisil Kòd nan pwogram nou an gwosè a nan tab la. Nan ka sa a, nou konnen gen nan pa janm plis pase 31 jou nan yon mwa. Se konsa, difisil kodaj yon valè tankou 31 rezonab nan ki kontèks. Nan kontèks la nan non, di kodaj 26 se pa rezonab li moun nan non sèlman kòmanse ak, pou egzanp, alfabè a ki enplike A jiska Z. Nou ka bachote yo tout nan ki done estrikti toutotan, lè nou jwenn yon kolizyon, nou pa mete non yo isit la, nou olye panse a selil sa yo pa tankou strings tèt yo, men kòm endikasyon, pou egzanp Alice,. Lè sa a, Alice ka gen yon lòt konsèy nan yon lòt Non kòmanse avèk A. Lè Bob aktyèlman ale sou isit la. Men, si gen nan yon lòt non kòmanse ak B, li fini moute sou isit la. Se konsa, chak nan eleman yo nan sa a tab de, si nou fèt sa a yon ti kras pi plis malen - vin sou - si nou fèt sa a plis yon ti kras malen, kounye a vin tounen yon done adaptasyon estrikti, kote gen nan pa gen limit difisil sou ki jan anpil eleman ou ka insert nan li paske si w fè gen yon kolizyon, ki nan amann. Jis ale pi devan epi kole li nan ki sa nou te wè yon ti jan de sa te li te ye kòm yon lis lye. Oke kite a pran yon poz sèlman pou moman yon. Ki pwobabilite a nan yon kolizyon an plas an premye? Dwa, petèt mwen sou panse, petèt Mwen se sou jeni pwoblèm sa a, paske ou konnen ki sa? Wi, mwen ka vini ak abitrè egzanp sou tèt la nan tèt mwen tankou Allison ak Arawon, men nan reyalite, bay yon distribisyon inifòm nan entrain, se sa ki kèk parusyon o aza nan yon estrikti done, sa ki vrèman se pwobabilite pou yon kolizyon? Oke vire soti, li la aktyèlman super segondè. Kite m 'jeneralizasyon sa a pwoblèm se tankou sa a. Se konsa, nan yon chanm nan n CS50 elèv yo, sa ki nan pwobabilite ki genyen pou omwen de elèv yo nan chanm nan gen menm jou fèt? Se konsa, gen nan sa. yon Hund kèk - 200, 300 moun isit la ak plizyè san moun nan kay la jodi a. Se konsa, si ou te vle mande tèt nou sa ki nan pwobabilite pou de moun nan sal sa a ki gen anivèsè nesans la menm, nou ka figi sa a soti. Apre sa, mwen fè reklamasyon aktyèlman ki te gen de moun ki gen anivèsè nesans la menm. Pou egzanp, fè yon moun gen anivèsè nesans jodi a? Yè? Denmen? Tout dwa, se konsa li santi l tankou mwen pral gen fè sa 363 oswa konsa plis fwa ki aktyèlman konnen si nou fè gen yon kolizyon. Oswa nou te ka jis fè sa a matematik olye ke tediously fè sa. Men, pwopoze sa ki annapre yo. Se konsa, mwen pwopoze ke nou te kapab modèl la pwobabilite nan de moun ki gen nan menm anivèsè nesans kòm pwobabilite a nan 1 mwens pwobabilite pou pa gen yon sèl ki gen anivèsè nesans la menm. Se konsa, yo ka resevwa sa a, ak sa a se jis nan anpenpan fason pou ekri sa a, pou la premye moun nan chanm nan, li oswa li te ka gen nenpòt youn nan posib nan anivèsè nesans asepte 365 jou nan ane a, ak ekskiz ak moun ki gen Fevriye 29 anivèsè nesans la. Se konsa, premye moun ki nan sal sa a se gratis gen nenpòt ki kantite anivèsè nesans soti nan posiblite yo 365 se konsa ke nou pral fè sa 365 divize pa 365, ki se youn. Moun nan pwochen nan sal la, si objektif la se pou fè pou evite yon kolizyon, ka sèlman gen li oswa anivèsè nesans li sou ki jan anpil diferan jou posib? 364. Se konsa, dezyèm tèm nan nan sa a ekspresyon ki esansyèlman fè sa matematik pou nou pa soustraksyon koupe yon sèl posib jou. Lè sa a, jou a kap vini an, jou kap vini an, pwochen jou desann nan kantite total moun ki nan sal la. Men, si nou lè sa a konsidere, ki sa ki Lè sa a, se pwobabilite a pa tout moun ki gen anivèsè nesans inik, men ankò mwens 1 sa, ki sa nou jwenn se yon ekspresyon ki ka trè fancifully gade tankou sa a. Men, li la plis enteresan gade nan vizyèlman. Sa a se yon tablo kote sou aks-x la se nimewo a nan moun ki nan sal la, kantite anivèsè nesans. Sou aks-y la pwobabilite nan yon kolizyon, de moun gen anivèsè nesans la menm. Men, Takeaway nan sa a soti nan koub la se ki le pli vit ke ou jwenn renmen 40 elèv yo, w ap moute nan yon pwobabilite 90% combinatorically nan de moun oswa plis ki gen anivèsè nesans la menm. Men, yon fwa ou jwenn nan renmen 58 moun li nan prèske 100% nan yon chans de la moun ki nan sal la yo ale nan gen nan anivèsè nesans menm, menm si gen nan 365 oswa 366 bokit posib, epi sèlman 58 moun ki nan sal la. Jis estatistik nou gen chans jwenn kolizyon, ki nan kout motive sa a diskisyon. Ke menm si nou jwenn anpenpan isit la, ak kòmanse gen sa yo chenn, nou ap toujou pral gen kolizyon. Se konsa, ki amèn kesyon an, ki sa ki la pri nan fè parusyon ak sipresyon nan yon estrikti done tankou sa a? Oke, kite m 'pwopoze - ak kite m 'ale tounen nan ekran an sou isit la - si nou te n eleman nan la lis, Se konsa, si nou ap eseye mete n eleman, epi nou gen konbyen bokit total manm? Se pou nou di 31 bokit total nan ka a nan anivèsè nesans. Ki sa ki nan longè a maksimòm de yon sèl nan sa yo chenn ki kapab? Si ankò gen nan 31 posib anivèsè nesans nan yon mwa bay yo. Epi nou jis ap agregasyon tout moun - aktyèlman sa a, se yon egzanp estipid. Se pou yo fè 26 pito. Se konsa, si gen aktyèlman moun ki gen non kòmanse ak A jiska Z, kidonk bay nou 26 posiblite yo. Epi nou ap itilize yon estrikti done tankou youn nan nou jis te wè, kijan nou gen yon etalaj de pwent, chak nan yo ki pwen nan yon lis nan lye kote lis premye se tout moun ak non Alice an. Lis la se dezyèm chak ak nan non kòmanse avèk A, kòmanse ak B, ak pou fè. Ki sa ki nan longè a gen anpil chans nan chak nan sa yo li bay lis si nou sipoze yon Netwaye bèl distribisyon non A jiska Z atravè estrikti nan done antye? Genyen n moun ki nan estrikti a done divize pa 26, si yo ap joliman pwopaje soti sou tout la done estrikti. Se konsa, longè a nan chak nan sa yo chenn ki n divize pa 26. Men, nan notasyon gwo O, ki sa ki sa? Ki sa ki se ki vrèman? Se konsa, li vrèman jis n, dwa? Paske nou te di nan sot pase a, ki pwa ou divize pa 26. Wi, an reyalite li se pi vit. Men, nan teyori, li pa fondamantalman tout sa ki pi vit. Se konsa, nou pa sanble yo gen tout sa ki anpil pi pre sa a grail apa pou Bondye. An reyalite, sa a se jis tan lineyè. Èk, nan pwen sa a, poukisa pa fè sa nou jis itilize yon sèl gwo lis lye? Poukisa nou pa jis itilize yon sèl gwo etalaj nan magazen non yo nan tout moun nan sal la? Oke, ki gen la toujou yon bagay konvenkan sou yon tab regle? Èske gen toujou yon bagay konvenkan sou yon estrikti done ki sanble ak sa a? Sa a. ELÈV: [fèbl]. Oratè 1: Dwa, epi ankò si li jis yon algorithm tan lineyè, ak yon lineyè tan done estrikti, poukisa pa fè sa mwen jis magazen Non tout moun nan yon gwo etalaj, oswa nan yon gwo lis lye? Epi yo sispann fè CS anpil pi rèd pase sa li bezwen yo dwe? Ki sa ki se konvenkan sou sa a, menm si m 'grate li soti? ELÈV: [fèbl]. Oratè 1: parusyon yo pa? Chè ankò. Se konsa, parusyon potansyèlman te ka toujou dwe konstan tan, menm si done ou estrikti sanble tankou sa a, yon etalaj de endikasyon, chak nan yo ki ap montre yon potansyèlman yon lis lye. -Ki te kapab ou reyalize konstan ensèsyon tan nan non? Bwa l 'la devan la, dwa? Si nou ofri bèt pou touye yon objektif konsepsyon soti nan pi bonè, kote nou te vle kenbe Non tout moun, pou egzanp, Ranje, oswa tout nan nimewo ki sou sèn Ranje, sipoze ke nou gen yon klase lis lye. Li sèlman koute nou youn oubyen de etap, renmen nan ka a nan Ben ak Brian pi bonè, insert yon eleman nan nan konmansman an nan lis la. Se konsa, si nou pa pran swen sou klasman tout nan non yo kòmanse avèk A oswa tout non yo kòmanse avèk B, nou kapab toujou reyalize konstan ensèsyon tan. Koulye a, leve je l 'Alice oswa Bob oswa Non nenpòt plis jeneralman se toujou ki sa? Li nan gwo O n divize pa 26, nan la ideyal ka kote tout moun nan egzakteman menm jan distribiye, kote ki gen nan kòm anpil A kòm gen nan Z, ki se pwobableman ireyèl. Men, sa a toujou lineyè. Men, isit la, nou tounen vin jwenn pwen an nan asenptotik notasyon yo te teyorikman vre. Men, nan mond reyèl la, si mwen reklamasyon ke pwogram mwen ka fè yon bagay 26 fwa pi vit pase ou, ki gen pwogram ou menm ki pral pito lè l sèvi avèk? Pou nou, oswa m 'yo ki se 26 fwa pi vit? Pli reyèlman, moun nan ki gen se 26 fwa pi vit, menm si teyorikman algoritm nou an kouri nan menm bagay la tou asenptotik kouri tan. Kite m 'pwopoze yon diferan solisyon tout ansanm. Men, si sa a pa kònen tèt ou, nou ap soti nan done estrikti. Se konsa, sa a se li yon trye - kalite yon non estipid. Li vini soti nan retrievals, ak pawòl Bondye a eple trye, t-r-mwen-e, paske nan Rekipere kou son tankou trye. Men, sa a istwa a nan trye an mo. Se konsa, yon trye se vre gen kèk kalite pye bwa, ak li la tou yon pyès teyat sou mo sa a. Men, menm si ou pa ka byen wè li ak sa a vizyalizasyon, yon trye se yon pye bwa estriktire, tankou yon pyebwa fanmi ki gen yon sèl zansèt nan tèt la ak anpil nan pitit pitit ak pitit pitit gwo kòm kite sou anba a. Men, chak ne nan yon trye se yon etalaj. Epi li nan yon etalaj - ak nan kite Senplifye pou yon moman - li nan yon etalaj, nan ka sa a, nan gwosè 26, kote chak ne ankò se yon etalaj de gwosè 26, kote zeroth eleman an nan ki etalaj reprezante A, ak dènye a eleman nan chak tankou etalaj reprezante Z. Se konsa, mwen pwopoze, Lè sa a, ke sa a done estrikti, yo konnen kòm yon trye, yo ka itilize tou nan magazen mo yo. Nou te wè yon ti moman de sa ki jan nou te ka sere mo, oswa nan sa a non ka, epi nou wè pi bonè ki jan nou ka magazen nimewo, men si nou konsantre sou non oswa strings isit la, avi sa ki nan enteresan. Mwen reklamasyon ke Maxwell nan non se andedan nan estrikti sa a done. Kote ou wè Maxwell? ELÈV: [fèbl]. Oratè 1: Sou bò gòch la. Se konsa, sa ki nan enteresan ak done sa yo estrikti a se olye ke magazen an fisèl M-A-X-W-E-L-L antislach zewo yo, tout kontigu, ki sa ou olye pou fè ap swiv. Si sa a se yon trye tankou estrikti done, chak nan nœuds ki gen se ankò yon etalaj, epi ou vle nan magazen Maxwell, ou premye endèks ak sa ne rasin a, se konsa yo pale, ne a topmost, nan kote M, dwa, se konsa apeprè nan mitan yo. Lè sa a, soti nan gen, ou swiv yon konsèy nan yon nœuds pitit, se konsa pale. Se konsa, nan sans nan pyebwa fanmi yo, ou swiv li anba. Epi ki mennen ou nan yon lòt ne sou bò gòch la a, ki se jis yon lòt etalaj. Lè sa a, si ou vle nan magazen Maxwell, ou jwenn konsèy la ki reprezante A, ki se yon sèl sa a isit la. Lè sa a, ou ale nan ne nan pwochen an. Ak Avi - sa a se poukisa foto a nan yon twonpe ti kras - sa a ne gade super ti. Men, sou bò dwat la nan sa a se Y ak Z yo Li nan jis te otè a twonke la foto pou ke ou aktyèlman wè bagay sa yo. Sinon foto sa a ta dwe lajman lajè. Se konsa, kounye a ou endèks nan kote X, Lè sa a, W, Lè sa a, E, lè sa a L, Lè sa a, L. Lè sa a, sa ki nan sa a kiryozite? Oke, si nou ap itilize sa a sòt de nouvo pran sou ki jan nan magazen yon kòd nan yon done estrikti, ou toujou bezwen esansyèlman tcheke nan done yo estrikti ki yon mo fini isit la. Nan lòt mo, chak nan sa yo nœuds yon jan kanmenm te sonje ke nou aktyèlman swiv tout moun sa yo endikasyon epi yo kite yon ti kras pen myèt nan pati anba a isit la nan sa a estrikti ki endike M-A-X-W-E-L-L se tout bon nan estrikti sa a done. Se konsa, nou ta kapab fè sa a jan sa a. Chak nan nœuds yo nan foto a nou jis wè gen yon sèl, yon etalaj de gwosè 27. Epi li kounye a 27, paske se nan p mete sis, nou pral aktyèlman ba ou yon apostwòf, pou nou ka gen non tankou O'Reilly ak lòt moun ak apostrof. Men, menm lide. Chak nan tout sa yo eleman nan la etalaj pwen nan yon struct ne, Se konsa, jis yon ne. Se konsa, sa a se trè okoumansman nan lye lis nou an. Lè sa a, mwen gen yon Boolean, ki Mwen pral rele mo, ki se jis yo pral vre si yon mo fini nan sa a ne nan pye bwa an. Li efektivman reprezante ti kras nan triyang nou te wè yon ti moman de sa. Se konsa, si yon mo fini a ki ne nan la pye bwa, ki jaden mo yo pral vre, ki se concept tcheke koupe, oswa nou ap fè desen sa a triyang, repons lan se wi gen se yon mo isit la. Se konsa, sa a se yon trye. Epi, koulye a kesyon an se, ki sa ki se li yo kouri tan? Èske li gwo O n? Èske li yon lòt bagay? Oke, si ou te n non sa a nan done estrikti, Maxwell yo te jis youn nan yo, sa ki se tan a kouri nan yo mete oswa jwenn Maxwell? Ki sa ki nan lè a kouri nan yo mete Maxwell? Si ta gen n lòt non deja nan tablo a? Yeah? ELÈV: [fèbl]. Oratè 1: Yeah, li nan longè nan non an, dwa? Se konsa, M-yon-x-W-e-L-l se konsa li santi l tankou sa a algorithm se gwo O nan sèt. Koulye a, nan kou, non ap varye nan longè. Petèt li nan yon Non kout. Petèt li nan yon Non dire pi lontan. Men, sa ki nan kle isit la se ke li nan yon nimewo konstan. E petèt li pa vrèman konstan, Men, Bondye, si pli reyèlman, nan yon diksyonè, gen nan pwobableman kèk limit sou kantite lèt nan yon Non moun nan nan yon peyi an patikilye. Se konsa, nou ka asime ke valè a se yon konstan. Mwen pa konnen sa li ye. Li pwobableman pi gwo pase nou panse li se. Se paske gen la toujou kèk kwen ka ak yon non fou lontan. Se konsa, kite a rele l 'k, men li la toujou yon konstan prezimableman, paske chak non nan mond lan, nan omwen nan yon peyi an patikilye, se ke longè oswa ki pi kout, se konsa li konstan. Men, lè nou te di yon bagay ki gwo O nan yon valè konstan, sa ki nan ke reyèlman ekivalan a? Sa a vrèman menm bagay la kòm li te di konstan tan. Koulye a, nou ap kalite fason ou kapab triche, dwa? Nou kalite swe kèk teyori isit la yo di ke byen, lòd k se vrèman jis lòd nan yon sèl, ak li lè konstan. Men, li vrèman se. Paske insight nan kle isit la se ke si nou te n non deja nan sa a done estrikti, epi nou insert Maxwell, se kantite tan li pran nou nan insert Maxwell nan tout ki afekte yo pa ki jan anpil lòt moun yo nan estrikti a done? pa sanble yo gen. Si mwen te gen yon milya dola plis eleman sa a trye, ak Lè sa a, insert Maxwell, se li nan tout afekte? No Epi sa a, kontrèman ak nenpòt ki nan done yo jou estrikti nou te wè konsa byen lwen, kote tan an kouri nan algorithm ou a konplètman endepandan de konbyen bagay la se oswa se pa deja nan ki estrikti done. Se konsa, avèk sa a pèmèt ou kounye a se yon opòtinite pou p, sis seri ki pral ankò gen pou wè ak mete ann aplikasyon pwòp ou a korektè, lekti nan 150,000 mo, ki jan pi bon nan magazen ki se pa nesesèman evidan. Epi menm si mwen te aspire jwenn grail a apa pou Bondye, mwen pa fè sa reklamasyon ke yon trye se. An reyalite, yon tab regle ka trè byen pwouve ke yo dwe pi plis efikas. Men, moun yo se jis - sa se sèlman youn nan desizyon ki konsepsyon w ap gen fè. Men, nan fèmen kite a pran 50 oswa konsa segonn yo pran yon gade vit nan sa ki bay manti devan nan semèn kap vini epi pi lwen, nou tranzisyon sa a soti nan liy lòd mond si C pwogram entènèt bagay sa yo ki baze ak lang tankou PHP ak JavaScript ak entènèt la poukont li, pwotokòl tankou HTTP, ki ou te pran pou yo akòde pou ane kounye a, ak tape pi chak jou, petèt, oswa wè. Epitou, n ap kòmanse kale do a kouch nan sa ki se entènèt la. Ak sa ki se kòd la ki fond zouti a jodi a. Se konsa, 50 segonn nan sa a kol isit la. M 'ba ou gèrye nan rezo a. [Lèktur videyo] -Li te vini ak yon mesaj. Avèk yon pwotokòl tout pwòp tèt li. Li vin nan yon mond nan firewall yo mechan, uncaring routeurs, ak danje lwen pi mal pase lanmò. Li nan vit. Li nan fò. Li nan TCPIP. Men, li a te gen adrès ou. Gèrye nan rezo a. [Lèktur videyo END] Oratè 1: Sa se ki jan entènèt la va travay kòm nan an semèn pwochèn.