[MIZIK jwe] 

Andi Peng: Byenveni nan semèn 3 nan seksyon. Mèsi, ou nèg, pou tout vini nan sa a kòmansman tan pi bonè jodi a. Nou te gen yon bèl, ti kras entim gwoup jodi a. Se konsa, èspere ke nou pral ale nan fini, petèt, byen bonè, yon ti jan bonè jodi a. Se konsa, byen vit, sèlman kèk anons pou ajanda a jodi a. Anvan nou kòmanse, nou ap ale nan jis ale sou kèk pwoblèm lojistik kout, pset kesyon, Debrief, bagay sa yo tankou sa. Lè sa a, nou pral plonje dwat nan. Nou pral sèvi ak yon debugjeur rele gdb kòmanse debunking Kòd nou an, ki David eksplike nan konferans lòt jou a. Nou pral ale sou kat kalite mouvman yo ak kalite. Nou pral ale sou yo trè byen vit depi yo ap trè entansif. Men, konnen ke tout glisad yo ak kòd sous yo toujou sou entènèt. Se konsa, santi yo lib, nan lèktur ou a, tounen ladan l epi pran yon gade nan sa. 

Nou pral ale nan asenptotik notasyon, ki se jis yon fason anpenpan a li di: "runtimes," kote nou gen O nan gwo, ki David eksplike nan konferans. Epi nou gen Omega, tou ki se ègzekutabl ki pi ba mare. Epitou, n ap pale yon ti jan pi plis approfondie konsènan ki jan moun travay. Epi anfen, nou pral ale sou binè rechèch, paske yon anpil nan nou ki te deja regarda nan psets ou pwobableman konnen ke ki se yon kesyon sa a, se nan pset ou yo. Se konsa, ou pral tout gen kè kontan ke nou kouvri sa a jodi a. 

Epi anfen, pou chak ou seksyon fidbak, mwen aktyèlman kite apeprè 15 minit nan fen a nan jis ale sou lojistik nan pset3, nenpòt kesyon, petèt yon ti jan nan konsèy, si ou pral, anvan nou kòmanse pwogram. Se konsa, kite a eseye jwenn nan materyèl la byen vit. Lè sa a, nou ka pase kèk tan pran plis kesyon pou pset la. OK. 

Byen vit, Se konsa, jis yon kèk anons anvan nou kòmanse jodi a. Pwemyeman, akeyi nan fè li nan de nan psets ou yo. Mwen te pran yon gade nan your-- yeah, se pou yo jwenn yon wonn nan aplodisman pou sa yon sèl. Aktyèlman, mwen te reyèlman, reyèlman enpresyone. Mwen resevwa nòt pset an premye pou ou nèg semèn ak ou nèg te fè dènye enkwayab. 

Style te sou pwen san konte yon kòmantè kèk. Asire ou ke ou ap toujou fè kòmantè kòd ou a. Men, psets ou te sou pwen. Epi kenbe l 'leve. Lè li nan bon pou elèv klas la wè ke ou nèg ap mete nan kòm anpil efò nan style ou ak konsepsyon ou nan kòd ou a ke nou ta renmen pou ou pou w wè. Se konsa, mwen pase sou gratitid mwen pou tout rès TAS yo. 

Sepandan gen yon kèk kesyon Debrief Mwen jis vle ale sou ki ta fè tou de lavi m ' ak yon anpil nan lòt la TAS 'ap viv yon ti jan pi fasil. Pwemyeman, mwen te remake sa a sot pase week-- ki jan anpil nan nou yo te kouri check50 sou Kòd ou anvan ou soumèt? OK. Se konsa, tout moun ta dwe ap fè check50, because-- yon secret-- nou aktyèlman kouri check50 kòm yon pati nan nou an Correct Scripts pou fè tès kòd ou a. Se konsa, si kòd ou a se li pap resevwa check50, nan tout chans, li la pwobableman ale nan fail chèk nou an kòm byen. Pafwa ou nèg gen repons yo dwat. Tankou, nan visye, kèk nan ou gen nimewo ki dwat, ou jis enprime soti kèk bagay siplemantè. Epi sa bagay anplis aktyèlman echwe chèk la, paske òdinatè a pa fè sa vrèman konnen ki sa li la kap chèche. Se konsa, li pral jis kouri nan, wè ke pwodiksyon ou pa fè sa matche ak sa nou espere repons lan yo dwe, epi make li se sa ki mal. 

Apre sa, mwen konnen sa ki te rive nan kèk nan ka ou semèn sa a. Se konsa, mwen te ale retounen lakay yo epi manyèlman rklase Kòd tout moun. Nan lavni an menm si, tanpri, tanpri asire w ke ke w ap kouri tcheke 50 sou kòd ou a. Paske li nan kalite yon doulè pou TA nan gen yo ale retounen lakay yo epi manyèlman regrade chak pset yon sèl pou chak sèl, ti kras rate egzanp. Se konsa, mwen pa t 'pran nan nenpòt pwen. Mwen panse ke mwen wete petèt youn oubyen de pou konsepsyon. Nan lavni an menm si, si w ap li pap resevwa check50, pwen pral pran konje pou Correct. 

Anplis de sa, yo se psets akòz vandredi 'midi a. Mwen panse ke gen nan yon sèt-minit an reta peryòd gras ke nou ba ou. Per tan Harvard, yo ap pèmèt yo gen sèt minit anreta nan tout bagay. Se konsa, isit la nan Yale, nou pral konfòme yo ak ki kòm byen. Men, bèl anpil, nan 12:07, si pset ou a pa an, li k ap pase yo dwe make kòm anreta. Se konsa, pandan ke li se te make kòm an reta, TA-- nan mwen se toujou ale nan dwe bay nòt psets ou yo. Se konsa, ou pral toujou wè yon nòt parèt. Sepandan, konnen ke nan nan fen semès la, tout psets an reta pral jis pou otomatikman zero pa òdinatè a. 

Nou fè sa pou de rezon. Youn, pafwa nou jwenn eskize, tankou eskiz dwayen an, pita sou ke mwen pa konnen sou ankò. Se konsa, nou renmen pou pi si nou ap bay nòt tout bagay jis nan ka, tankou, mwen se manke eskiz yon dwayen an. Ak Dezyèmman, kenbe nan tèt ou, ou kapab toujou lage yon sèl pset ki gen pwen sijè ki abòde plen. Se konsa, nou renmen klas yo tout nan psets ou jis a asire w ke sijè ki abòde ou a gen ak w ap eseye yo. Se konsa, menm si li nan an reta, ou pral toujou jwenn kredi pou pwen sijè ki abòde, mwen panse ke. 

Se konsa, moral nan istwa a se, fè asire w psets ou yo nan sou-tan. Men, si yo menm yo pa an sou-tan, konnen ke li nan pa gwo. Yeah, mwen anvan m 'deplase sou, nenpòt moun ki gen nenpòt kesyon konsènan fidbak pset? Yeah. 

ODYANS: Èske ou te di nou ka lage youn nan psets yo? 

Andi Peng: Yeah. Se konsa, gen nan nèf psets jeneral sou kou a nan semès la. Men, si ou gen sijè ki abòde pwen- konsa sijè ki abòde se jis, bèl anpil, ou menm ki eseye nan pwoblèm, ou menm ki mete nan tan, ou menm ki ki montre ke ou te demontre ou te li espèk a. Sa a bèl anpil sijè ki abòde. Men, si w ap ranpli pwen sijè ki abòde, nou ka lage ki pi ba a yon sèl soti nan sijè ki abòde plen. Se konsa, sa a, se nan avantaj ou nan ranpli epi eseye chak pset. 

Menm si Pa gen yonn nan téléchargement yo travay, Upload yo tout. Lè sa a, nou pral èspere ke pral kapab ba ou kèk nan pwen sa yo tounen. Fre. Nenpòt lòt kesyon? Great. 

Dezyèmman, biwo hours-- yon kèk nòt rapid sou lè biwo. Se konsa, premye, vini byen bonè nan semèn nan. Pa gen moun ki se tout tan an lè biwo sou lendi. Christabel rive lè biwo yè swa. Yeah, Christabel. Ak sa ki t 'nou gen nan biwo èdtan yè swa, Christabel? 

ODYANS: Nou te gen krèm glase. 

Andi Peng: Se konsa, sa a, se dwa, nou te gen krèm glase a lè biwo yè swa. Pandan ke mwen pa ka pwomèt ou ke nou pral gen krèm glase a lè biwo chak semèn, ki sa mwen kapab pwomèt ou se ke pral gen yon anpil pi bon elèv nan TA rapò. Fè tankou legi, li la tankou twa nan yon sèl. Lè nou konsidere ke, diferansye ke ak Jedi, ou te gen sou 150 reyèlman ensiste timoun yo ak pa gen okenn krèm glase. Lè li nan jis pa pwodiktif pou nenpòt ki moun. Se konsa, moral nan istwa a se, vin byen bonè biwo heures Et bon bagay pral rive. 

Epitou, vini prepare yo poze kesyon. Ou konnen? Kèlkeswa sa TAS, mwen panse, yo te di: nou ve yo te ap resevwa yon koup elèv yo ki moun ki vini nan nan Jedi nan, tankou, 10:50 pa gen li espèk a ke yo te tankou ede m ', ede m'. Malerezman nan pwen sa a, gen nan pa anpil nou ka fè ede ou. Se konsa, tanpri vini yo byen bonè nan semèn nan. Vini non bonè yo lè biwo. Vini non prepare yo poze kesyon. Asire w ke ou, kòm yon elèv, yo se kote ou bezwen yo dwe lè sa a, nan TAS kapab gide ou ansanm, ki se sa ki lè biwo Yo ta dwe attribué pou. 

Dezyèmman, se konsa mwen konnen pwofesè renmen sipriz nou ak tès yo. Mwen te gen yon pwofesè moun tankou, Yo, nan chemen an, sonje ke A. Kilès ou gen Lendi pwochen. Yeah, mwen pa t 'konnen sou sa A. Kilès. Se konsa, mwen pral yo dwe ki TA ki raple nou tout ki egzamen 0-- paske, ou konnen, nou ap CS. Kounye a ke nou te ranje fè, ou jwenn poukisa li a egzamen 0, pa poze 1, eh? OK. Oh, mwen te resevwa kèk chuckles sou sa yon sèl. OK. 

Se konsa, egzamen 0 yo pral Oktòb 14 si w ap nan seksyon an Lendi-Mèkredi ak 15 oktòb si w ap nan seksyon nan Madi-Jedi. Sa a pa aplike pou moun nan nou nan Harvard who-- Mwen panse ke ou pral tout ap pran ti tès ou sou 14th la. 

Se konsa, yeah, semèn pwochèn, si David, nan konferans, ale, yeah, se konsa sou sa egzamen semèn pwochèn, nou tout pa pral choke paske ou te vin nan seksyon epi ou konnen ke ou egzamen 0 se nan de semèn. Epitou, n ap gen revizyon sesyon ak tout bagay. Se konsa, pa gen enkyetid sou ke yo te pè pou sa. Nenpòt kesyon devan l nenpòt kesyon nan tout konsènan pwoblèm lojistik, nòt, lè biwo, seksyon? Yeah. 

ODYANS: Se konsa, egzamen an se pral fè pandan konferans? 

Andi Peng: Yeah. Se konsa, egzamen an, mwen panse, se 60 minit attribué nan ki plas tan ke ou pral jis pran nan sal la konferans. Se konsa, ou pa bezwen vini nan sou li a, tankou, yon o aza 7:00 PM. Li nan tout bon. Yeah. Fre. 

Tout dwa. Se konsa, nou ap ale nan prezante yon konsèp bay ou semèn sa a ke David te deja kalite a manyen sou nan konferans semèn sa a sot pase yo. Yo rele li gdb. Ak ki jan anpil nan nou, pandan ke yo nan kou a nan ekri psets ou, remake gen yon gwo bouton ki di "Debug" sou tèt la nan IDE ou a? OK. Se konsa, kounye a nou pral aktyèlman ale nan detire mistè a nan ki sa sa bouton aktyèlman fè. Apre sa, mwen garanti ou, li se yon bèl, bèl bagay. 

Se konsa, moute jouk koulye a, mwen panse ke gen te gen de bagay sa yo elèv yo te tipikman fè lè debogaj psets. Youn, yo swa ajoute nan printf () - Se konsa, chak liy kèk, yo ajoute nan yon printf () - oh, ki sa ki varyab sa a? Oh, ki sa ki sa a varyab now-- epi ou kalite wè pwogresyon nan a kòd ou a kòm li kouri. Ou metòd la dezyèm timoun fè se yo ke yo jis ekri tout bagay la ak Lè sa a ale tankou sa a nan fen an. Nou swete ke li fonksyone. Mwen garanti ou, gdb se pi bon pase tou de nan metòd sa yo. Yeah. Se konsa, sa a yo pral nouvo pi bon zanmi ou yo. Paske li nan yon bèl bagay ki vizyèlman montre tou de sa kòd ou a ap fè nan yon pwen espesifik osi byen ke sa ki tout nan ou varyab ap pote, tankou sa valè yo ye a, nan pwen sa a espesifik. Ak nan fason sa a, ou kapab reyèlman mete breakpoints nan kòd ou yo. Ou ka kouri nan liy pa liy. Apre sa, gdb pral jis gen pou ou, parèt pou ou, sa ki tout nan varyab ou yo, ki sa nou jwenn fè, sa k ap pase nan kòd la. Apre sa, nan yon fason, li nan tèlman pi fasil yo wè sa k ap pase olye pou yo printf-ING oswa ekri desann deklarasyon ou yo. 

Se konsa, nou pral fè yon egzanp sou sa a pita. Se konsa, sa sanble yon abstrè ti jan. Pa gen enkyetid, nou pral fè egzanp. Se konsa, esansyèlman, twa pi gwo, nan pi-itilize fonksyon ou pral bezwen nan gdb se Next a, Etap sou yo, ak Etap nan bouton ki sanble. Mwen pral tèt sou a, aktyèlman, kounye a. 

Se konsa, ou nèg tout ka wè ke oswa mwen ta dwe rale nan yon ti jan? Nan do a, ka ou wè sa? Èske mwen ta dwe rale nan? Jis yon ti jan ti kras? OK, fre. Gen nou ale. OK. 

Se konsa, mwen gen, isit la, mwen aplikasyon pou visye. Epi pandan ke y yon anpil nan ou nèg te ekri visye nan pandan y ap riban form-- ki se yon fason parfe akseptab fè l-- yon lòt fason yo fè l 'se tou senpleman divize an modulo la. Paske lè sa a ou ka gen ou valè ak Lè sa a, gen rès ou yo. Lè sa a, ou ka jis ajoute li tout ansanm. Èske lojik nan sa m ap fè isit la fè sans a tout moun, anvan nou kòmanse? Kalite? Fre. Great. Li se yon moso bèl sexy nan kòd, mwen ta ka di. Tankou mwen te di, David, nan konferans, apre yo fin yon ti tan, ou pral kòmanse wè tout Kòd kòm yon bagay sa a, se bèl. Epi pafwa lè ou wè bèl kòd, li la tankou yon santi bèl bagay. 

Se konsa, sepandan, tou sa a se trè Kòd bèl, li pa travay byen. Se konsa, kite a kouri check50 sou sa. Tcheke 50 20-- op. 2? Eske se sa ke pset2? Yeah. Oh, pset1. OK. Se konsa, nou kouri check50. 

Ak jan ou nèg ka wè isit la, li nan li pap resevwa yon koup la ka. Se pou kèk nan nou, nan la kou pou fè kouche pwoblèm ou an, w ap tankou, ah, poukisa se pa li ap travay. Poukisa li ap travay pou kèk valè men se pa pou lòt moun? Oke, gdb ki pral ede w figi konnen poukisa moun entrain pa te ap travay. 

OK. Se konsa, kite a wè, youn nan la chèk mwen te li pap resevwa nan check50 te valè a opinyon nan 0.41. Se konsa, repons ki kòrèk la ki ou ta dwe ap resevwa se yon 4. Men, olye pou sa m'ap enprime soti se 3-n a, ki se kòrèk. Se konsa, kite yo jis kouri sa a manyèlman, jis asire w ke check50 ap travay. Se pou yo fè ./greedy. Wouch, mwen gen fè visye. Gen nou ale. Koulye a, ./greedy. 

Konbyen se dwe? Se pou yo fè 0.41. Epi YEP, nou wè isit la ke li nan sorti 3 lè repons ki kòrèk la, an reyalite, yo ta dwe 4. Se konsa an n antre nan gdb ak wè kòman nou ka ale sou repare-pwoblèm sa a. 

Se konsa, premye etap la nan toujou debogaj kòd ou a se yo mete yon breakpoint, oswa yon pwen nan ki ou vle òdinatè a nan oswa debugjeur yo kòmanse gade nan. Se konsa, si ou pa fè sa vrèman konnen ki sa pwoblèm ou ye, se anjeneral, bagay la tipik nou vle fè se yo mete breakpoint nou an nan prensipal la. Se konsa, si ou nèg ka wè sa a bouton wouj dwat la, Oui, ki te m 'mete yon breakpoint pou fonksyon prensipal la. Mwen klike sa. 

Lè sa a, mwen ka ale jiska bouton Debug mwen. Mwen frape ki bouton. Kite m 'rale tounen konnen si mwen kapab. Gen nou ale. Se konsa, nou gen, isit la, yon panèl sou bò dwat la. Mwen regrèt sa, mesye nan do a, ou pa ka vrèman wè vrèman byen. Men, esansyèlman, tout panèl dwa sa-a ap fè se kenbe tras nan make nan tou de liy, ki se liy lan nan kòd ke òdinatè a se kounye a kouri, osi byen ke tout nan varyab ou desann isit la. 

Se konsa, ou te gen santim, pyès monnen, n, tout te deklare yo bagay sa yo diferan nan pwen sa. Pa gen enkyetid, paske nou gen pa aktyèlman inisyalizèd yo nan nenpòt varyab ankò. Se konsa, nan òdinatè w lan, ou òdinatè nan jis wè, oh, 32767 te dènye fonksyon an itilize nan ki espas memwa nan òdinatè mwen an. Se konsa, sa a, se kote santim kounye a se. Men, pa gen ke yon fwa ou kouri kòd la, li ta dwe vin inisyalizèd. 

Se konsa nou ale nan, liy pa liy, sa k ap pase isit la. OK. Se konsa, moute isit la yo se twa nan bouton ke mwen jis te esplike. Ou gen Jwe a, oswa fonksyon an Run, bouton, ou gen Etap la sou bouton, epi ou yo te genyen tou Etap la nan bouton. Apre sa, esansyèlman, tout twa nan yo jis ale nan kòd ou a ak fè bagay diferan. 

Se konsa, tipikman, lè w ap debogaj, nou pa vle jis frape Jwe, paske Jwe pral jis kouri kòd ou a nan fen an nan li. Lè sa a, ou pa pral aktyèlman konnen ki sa pwoblèm ou se sof si ou mete plizyè breakpoints. Si ou mete plizyè breakpoints, li pral jis otomatikman kouri soti nan yon breakpoint, nan pwochen an, pwochen an. Men, nan ka sa a nou te sèlman sa yon sèl, paske nou vle travay wout nou depi anwo desann jouk anba. Se konsa, nou ap ale nan inyore ki bouton kounye a pou rezon nan pwogram sa a. 

Se konsa, Etap la sou fonksyon jis etap sou tout sèl liy epi li di ou sa òdinatè a ap fè. Etap la nan fonksyon ale nan fonksyon an vrè sa a, se sou liy ou nan kòd. Se konsa, pou egzanp, tankou printf (), ki se yon fonksyon, dwa? Si mwen te vle fizikman etap nan printf () fonksyon an, Mwen ta aktyèlman ale nan yon moso postal kote printf () te ekri ak wè sa k ap pase a. 

Men, tipikman, nou asime ke Kòd la ke nou ba ou ap travay. Nou sipoze printf a () ap travay. Nou asime ke GetInt () ap travay. Se konsa, gen nan pa gen bezwen etap nan sa yo fonksyon. Men, si gen nan fonksyon ke ou ekri tèt ou ke ou vle tcheke soti sa k ap pase sou li a, ou ta vle nan etap nan ki fonksyon. 

Se konsa, kounye a nou ap jis ale nan etap sou pyès sa a nan kòd. Se konsa, kite a wè. Oh, enprime, "O hai, Ki jan se pi chanjman dwe? " Nou pa pran swen. Nou konnen ki nan travay, se konsa nou etap sou li. 

Se konsa, n, ki se flote nou an ki nou te initialized-- oswa declared-- moute nan tèt la, nou ap kounye a egal ke yo GetFloat (). Se konsa nou etap sou sa. Apre sa, nou wè nan a anba isit la, pwogram lan se pouse m 'nan opinyon yon valè. Se konsa, nan opinyon kite valè a nou vle li teste isit la, ki se 0.41. Great. 

Se konsa, kounye n-- fè ou nèg wè isit la, nan bottom-- a li nan stored-- paske nou pa gen awondi ankò, li nan ki estoke nan sa a jeyan tankou flote se sa ki 0,4099999996, ki se yo ase pre nou an rezon, kounye a, nan 0.41. Lè sa a, nou pral wè pita sou, menm jan nou kontinye kite sou pwogram nan, apre isit la, n te vin devni awondi ak santim te vin 41. Great. Se konsa, nou konnen ke k ap travay awondi nou an. Nou konnen ke nou gen nan Nimewo kòrèk la nan santim, se konsa nou konnen ke sa a, se pa reyèlman pwoblèm nan. 

Se konsa, nou kontinye kite pase nan pwogram sa a. Nou ale isit la. Se konsa, apre liy sa a nan kòd, nou ta dwe konnen ki jan anpil trimès nou genyen. Nou etap sou. Epi ou wè nou, an reyalite, gen yon sèl sezon paske nou te soustrè 25 de valè inisyal nou an 41. Epi nou gen 16 bò gòch pou santim nou an. 

Tout moun konprann ki jan pwogram nan se kite a e poukisa santim gen kounye a vin 16 e poukisa, kounye a, pyès monnen te vin devni 1? Èske tout moun sa yo ki lojik? Fre. Se konsa, kòm nan pwen sa a, nan k ap travay pwogram nan, dwa? Nou konnen li a fè egzakteman ki sa nou vle l 'bay. Apre sa, nou pa t 'aktyèlman gen enprime soti, o, ki sa se santim nan pwen sa a, ki sa ki pyès monnen nan pwen sa. 

Nou kontinye ale atravè tout pwogram nan. Etap sou. Fre. Nou ale sou dis kòb. Great. Nou wè ke li nan pran koupe $ 0.10 pou yon pyès dis santim ameriken. Epi, koulye a nou gen de pyès monnen. Sa a kòrèk. 

Nou ale sou peni epi nou wè ke nou te te resevwa rete sou santim. O o, sa a, se etranj. Moute isit la nan pwogram nan, mwen te sipoze yo te soustrè peni mwen. Petèt mwen jis pa t ' fè sa dwat liy. Apre sa, Ay, ou ka wè isit la, paske nou konnen ke nou ap kite nan liy 32 ak 33, sa a, se kote pwogram nou an mal te gen varyab kouri. Se konsa, nou ka gade ak wè, o, M 'ap soustraksyon santim isit la, men mwen pa aktyèlman ajoute nan valè pyès monnen mwen. M 'ap ajoute nan santim. Apre sa, mwen pa vle pou ajoute pou santim, mwen vle pou ajoute pou pyès monnen. Se konsa, si nou chanje ke yo pyès monnen, nou te gen yon pwogram k ap travay. Mwen ka kouri check50. Ou ka jis sòti soti nan gdb dwat isit la ak Lè sa a, kouri check50 ankò. Mwen te kapab jis fè sa. Mwen gen fè visye. 0.41. Ak isit la, li nan enprime soti repons kòrèk la. 

Se konsa, kòm ou nèg ka wè, gdb se yon zouti vrèman pwisan pou lè nou gen anpil Kòd ale sou ak pou anpil varyab ke li nan difisil pou nou, tankou yon moun, nan kenbe tras nan. Òdinatè a, nan gdb a debugjeur, gen kapasite nan nan kenbe tras nan tout bagay. Mwen konnen, nan Visionaire, ou nèg pwobableman ta ka yo frape kèk fot segmentation paske ou te kouri soti nan avèk limit nan etalaj ou yo. Nan egzanp lan nan Seza tande kòz, sa se ekzakteman ki sa mwen te aplike isit la. 

Se konsa, mwen bliye tcheke pou sa ki ka rive si mwen pa t 'gen de agiman liy lòd. Mwen jis pa t 'mete nan ki chèk la. Se konsa, si mwen kouri Debug-- mwen mete breakpoint mwen an la a. Mwen kouri Debug. 

OK. Yeah. Se konsa, aktyèlman, gdb te sipoze yo te di m 'gen te yon fòt segmentation la. Mwen pa konnen sa te ale sou dwa gen, men lè mwen kouri li, li te travay. Lè ou kouri liy nan Kòd nan ak Gdb ta ka jis toudenkou kite sou ou, al fè yo gade ki sa erè a wouj se. Li pral di ou, hey, ou te gen yon fay segmentation, ki vle di ke ou te eseye aksè espas nan yon etalaj ki pa t 'egziste. Yeah. 

Se konsa, nan pwoblèm nan pwochen mete semèn sa a, ou nèg pwal pwobableman gen yon anpil nan varyab waf alantou. Ou pa ap ale nan dwe fin sèten sa ki yo tout vle di nan yon pwen sèten. Se konsa, gdb pral reyèlman ede w nan lè n ap kalkile konnen ki sa ki yo, yo tout egal ak ke yo te kapab wè ke vizyèlman. Èske nenpòt moun ki konfonn sou kòman nenpòt nan ki te travay? Fre. Tout dwa. Se konsa, apre sa, nou se ale nan plonje dwat nan yo se kat diferan kalite kalite pou semèn sa a. Konbyen nan ou, premye nan tout, anvan nou kòmanse, te li espèk a tout antye pou pset3? OK. Mwen se fyè de ou nèg. Sa a tankou mwatye nan klas la, ki se siyifikativman plis pase dènye fwa. 

Se konsa, ki nan gwo, paske lè nou pale sou sa ki ekri nan lecture-- oswa regrèt sa, nan section-- Mwen renmen gen rapò yon anpil nan ki tounen nan sa pset a se ak ki jan ou vle aplike ke nan pset ou yo. Se konsa, si ou vin gen li espèk a, li pral gen yon anpil pi fasil pou ou pou w konprann sa m ap pale de lè m 'di, oh hey, sa a ta kapab yon vrèman bon plas yo aplike sa a sòt. Se konsa, moun nan nou ki te li nan SPEC konnen ke, kòm yon pati nan pset ou, w ap ale nan gen yo ekri yon di ki kalite sòt. Se konsa, sa a pouvwa ap trè itil pou yon anpil nan nou jòdi a. 

Se konsa, nou pral kòmanse koupe ak, esansyèlman, kalite a ki pi senp nan sòt, sòt seleksyon an. Algorithm nan tipik pou ki jan nou ta ale sou sa a is-- David mache ale nan tout sa yo tout nan konferans, se konsa mwen pral byen vit trennen sou isit lan-- se esansyèlman, ou gen yon etalaj de valè. Lè sa a, ou jwenn nan pi piti valè triye epi ou swap ke valè ak premye valè ki klase. Lè sa a, ou jis kenbe repete ak rès la nan lis ou a. 

Ak isit la nan yon eksplikasyon vizyèl nan ki jan ki ta travay. Se konsa, pou egzanp, si nou te kòmanse ak yon etalaj de senk eleman, endèks 0 a 4, ak 3, 5, 2, 6, ak 4 valè mete yo nan array-- a pou kounye a, nou ap jis ale nan asime yo ke yo ap tout triye paske nou pa te teste otreman. 

Se konsa, kouman yon sòt seleksyon ta travay se ke li ta premye kouri nan antye a nan etalaj ki klase. Li ta chwazi soti valè a pi piti a. Nan ka sa a, 3, dwa kounye a, se pi piti a. Li vin nan 5. Non, 5 pa janm pi grannèg than-- oswa regrèt sa, se pa mwens than-- 3. Se konsa, valè minimòm-nan se toujou 3. Lè sa a, ou jwenn yo 2. Òdinatè a wè, o, 2 se mwens pase 3. 2 yo dwe kounye a dwe valè a minimòm. Se konsa, 2 echanj ak sa premye valè. 

Se konsa, apre yon pas, nou tout bon wè ke 2 an ak 3 an yo échanges. E nou jis ale nan kontinye fè sa a ankò ak rès la nan etalaj la. Se konsa, nou ap ale nan jis kouri nan kat dènye endis yo nan etalaj la. Nou pral wè ke 3 se pwochen valè minimòm-nan. Se konsa, nou ap ale nan swap ke ak 4. Lè sa a, nou ap jis ale nan kenbe kouri nan jouk, evantyèlman, ou li ale nan yon etalaj Ranje nan ki 2, 3, 4, 5, ak 6, yo tout Ranje. Tout moun konprann lojik la nan ki jan yon sòt seleksyon travay? 

Ou jis gen kèk sòt nan yon valè minimòm. W ap kenbe tras nan ki sa sa se. Chak fwa ou jwenn li, ou swap li ak valè a an premye nan array-- nan oswa, pa value-- an premye valè nan pwochen nan etalaj la. Fre. 

Se konsa, kòm ou nèg kalite wè ki sòti nan yon aperçu kout, nou ap ale nan pseudocode sa a soti. Se konsa, si ou nèg nan do a vle fòme yon gwoup, tout moun nan yon tablo ka fòme yon ti kras patnè, mwen pral bay ou nèg tankou twa minit jis pale a lojik la, nan lang angle, nan ki jan nou ta ka kapab aplike pseudocode yo ekri yon sòt seleksyon. Apre sa, nan sirèt. Tanpri souple, vin leve, li jwenn sirèt. Si ou se nan do a, epi ou vle sirèt, mwen ka voye jete sirèt nan ou. Aktyèlman, fè you-- fre. Oh, regrèt. OK. 

Se konsa, si nou ta renmen, kòm yon klas, ekri pseudocode pou konbyen ki ta ka yon apwòch pwoblèm sa a, jis santi yo lib. Mwen pral jis ale nan, epi, yo nan lòd, mande gwoup pou liy nan pwochen nan ki sa nou ta dwe ap fè. Se konsa, si ou nèg vle kòmanse koupe, sa ki nan premye bagay la w dwe fè lè w ap eseye aplike yon fason yo rezoud pwogram sa a oaza sòt yon lis? Se pou nou jis asime nou gen yon etalaj, tout dwa? 

ODYANS: Ou vle kreye kèk sòt de [fèbl] ke w ap kouri nan tout etalaj ou yo. 

Andi Peng: Dwa. Se konsa, w ap ale nan vle repekte nan chak espas, dwa? Se konsa, gwo. Si ou nèg vle bay nan m ' pwochen line-- yeah, nan do an. 

ODYANS: Tcheke yo tout pou pi piti a. 

Andi Peng: Gen nou ale. Se konsa, nou vle ale nan ak tcheke yo wè sa ki valè a minimòm-nan se, dwa? Mwen pral abreje ki nan "min." Ki sa ou mesye vle fè apre ou te jwenn valè minimòm-nan? 

ODYANS: [fèbl] Andi Peng: Se konsa, w ap ale nan vle chanje l 'ak premye a nan ki etalaj, dwa? Sa a nan konmansman an, mwen pral di yo. Tout dwa. Se konsa, kounye a ke ou te échanges premye a yon sèl, ki sa ou vle fè apre sa? Se konsa, kounye a nou konnen ke sa a yon sèl isit la dwe valè ki pi piti a, dwa? Lè sa a, ou gen yon rès adisyonèl nan etalaj la sa a, se triye. Se konsa, sa ou vle fè isit la, si ou mesye vle ban m 'liy vin apre a? ODYANS: Se konsa, Lè sa a, ou vle repekte a rès la nan etalaj la. Andi Peng: Yeah. Se konsa, sa ki iteration nan kalite vle di nou pral pwobableman bezwen? Ki kalite de- 

ODYANS: Oh, yon varyab adisyonèl? Andi Peng: Pwobableman yon lòt pou riban, dwa? Se konsa, nou ap pwobableman ale nan vle repekte nan gwo. Lè sa a, w ap ale nan tounen ladan l epi pwobableman tcheke minimòm la ankò, dwa? Apre sa, w ap ale nan kenbe repete sa a, paske pasan yo jis ale kenbe kouri, dwa? 

Se konsa, kòm ou nèg ka wè, nou jis gen yon pseudocode jeneral nan ki jan nou vle pwogram sa a yo gade. Repekte sa a isit la, sa nou fè tipikman bezwen ekri nan kòd nou an si nou vle repekte nan yon etalaj, ki kalite estrikti? Mwen panse ke Christabel deja di sa a anvan. 

ODYANS: A pou riban. 

Andi Peng: Yon pou riban? Egzakteman. Se konsa, sa a se pwobableman pral gen yon pou riban. Ki sa ki se yon chèk isit la ale nan vle di? Tipikman, si ou vle tcheke si gen yon bagay se yon bagay else-- 

ODYANS: Si. 

Andi Peng: Yon si, dwa? Lè sa a, swap a isit la, nou pral ale sou pita, paske David mache ale nan tout ke nan konferans kòm byen. Lè sa a, dezyèm repekte nan implique 

ODYANS: Yon lòt pou riban. 

Andi Peng: --another pou riban, egzakteman. Se konsa, si nou ap chèche nan nivo sa a kòrèkteman, nou ka wè ke nou ap pwobableman ale nan bezwen yon enbrike pou riban ak yon deklarasyon kondisyonèl nan la ak Lè sa a yon moso reyèl nan Kòd sa a, se ale nan swap valè yo. Se konsa, mwen te jis jeneralman ekri yon kòd pseudocode isit la. Lè sa a, nou ap aktyèlman pral fizikman, tankou yon klas, eseye aplike sa a jodi a. Ann al tounen nan IDE sa a. 

Uh-oh. Poukisa se ke not-- gen li ye. OK. Padon, kite m 'eseye rale nan yon ti jan plis. Gen nou ale. Tout sa mwen ap fè isit la se mwen te kreye yon pwogram yo rele "seleksyon / sort.c." Mwen te kreye yon etalaj de nèf valè, 4, 8, 2, 1, 6, 9, 7, 5, 3. Kounye a, menm jan ou kapab wè yo, yo se unordered. N a pwal nimewo a ki di ou kantite lajan an nan valè ou gen nan etalaj ou yo. Nan ka sa a, nou gen nèf valè. Apre sa, mwen te jis te resevwa yon pou riban isit la ki simagri soti etalaj ki klase. 

Apre sa, nan fen a, Mwen te tou te resevwa yon pou bouk ki jis simagri li soti ankò. Se konsa, teyorikman, si pwogram sa a ap travay yo kòrèkteman, nan fen a, ou ta dwe wè yon enprime pou riban nan ki 1, 2, 3, 4, 5, 6, 7, 8, 9 yo tout kòrèkteman nan lòd. 

Se konsa, nou te gen pseudocode nou an isit la. Nenpòt moun ki vle to-- Mwen jis pral ale mande pou volunteers-- fè m 'konnen ekzakteman ki sa yo tape si nou vle, premye, jis repekte a nan konmansman an nan sa a etalaj? Ki sa ki nan liy la nan kòd mwen se pwobableman ale nan bezwen isit la? 

ODYANS: [fèbl] 

Andi Peng: Yeah, santi gratis regrèt to--, ou pa gen kanpe santi leve- lib yo leve vwa ou yon ti jan. 

ODYANS: Pou int mwen egal 0-- 

Andi Peng: Yeah, bon. 

ODYANS: mwen se mwens pase etalaj longè. 

Andi Peng: Se konsa, kenbe nan lide isit la, paske nou pa gen yon fonksyon ki di nou longè a nan yon etalaj, nou deja genyen yon valè ki estoke sa. Dwa? Yon lòt bagay kenbe nan mind-- nan yon etalaj nan nèf valè, ki sa yo endis yo? Se pou nou jis di etalaj sa a te 0 a 3. Ou wè ke dènye a endèks se aktyèlman 3. Li pa 4, menm si gen nan kat valè nan etalaj la. 

Se konsa, nan isit la, nou gen dwe pran anpil prekosyon nan sa ki kondisyon nou an pou longè a ki pral yo dwe. 

ODYANS: pa Li ta dwe n mwens 1? Andi Peng: Li k ap pase n mwens 1, egzakteman. Èske sans sa fè, poukisa li nan n mwens 1, tout moun? Li nan paske ranje yo se zewo-Catalogue. Yo kòmanse nan 0 ak kouri moute nan n mwens 1. Yeah, li nan yon ti jan difisil. OK. Apre sa, then-- ODYANS: Isnt'1 ki deja pran swen nan menm si, pa jis pa li di: "mwens pase oswa egal a "ak jis li di:" mwens pase? " 

Andi Peng: Sa se yon reyèlman bon kesyon. Se konsa, repons lan se wi. Men, tou, wout la ke nou ap mete ann aplikasyon dwat a kont kouran, ou bezwen konpare de valè. Se konsa, ou aktyèlman vle kite "nan" vid la. Paske si ou konpare yon sèl sa a, ou pa ap ale gen anyen apre li fin yo konpare a, dwa? Yeah. Se konsa, mwen ++. Se pou nou ajoute parantèz nou yo nan. Whoops. Great. Se konsa, nou gen nan konmansman an nan riban deyò nou an. Se konsa, kounye a nou pwobableman vle kreye yon varyab pou kenbe tras ki gen valè ki pi piti a, dwa? Nenpòt moun ki vle bay nan m ' liy nan kòd ki ta fè sa? Ki sa nou bezwen si nou ap ale vle nan magazen yon bagay? 

Dwa. Petèt yon non pi bon pou ki ta be-- "temp" totalman fonctionne- petèt yon pi plis justesse yo te rele ta dwe, si nou vle value-- ki pi piti a 

ODYANS: Min. Andi Peng: min, gen nou ale. min ta bon. Se konsa, isit la, sa nou fè vle inisyalize li nan? Sa a se yon ti jan difisil. Paske kounye a nan la kòmanse nan etalaj sa a, ou pa t 'gade yon bagay, dwa? Se konsa, sa, otomatikman, si nou ap jis sou mwen egal 0, ki sa nou vle inisyalize valè premye minimòm nou yo? ODYANS: mwen. Andi Peng: mwen, egzakteman. Christabel, poukisa nou vle inisyalize li nan mwen? 

ODYANS: Paske, byen, nou ap kòmanse avèk 0. Se konsa, paske nou pa gen anyen yo konpare l 'bay, minimòm la pral yo te fini 0. 

Andi Peng: Egzakteman. Se konsa, li la egzakteman dwat. Paske nou gen pa aktyèlman gade anyen ankò, nou pa konnen ki sa valè minimòm nou an, se. Nou vle jis inisyalize li nan m, ki, kounye a, se dwa isit la. Apre sa, pandan n ap kontinye deplase desann etalaj sa a, nou pral wè sa, youn ak plis pase, mwen ogmantasyon. Se konsa, nan pwen sa a, mwen se pwobableman pral vle yo dwe minimòm lan, paske li k ap pase yo dwe tou sa se nan konmansman an nan etalaj ki klase. Fre. 

Se konsa, kounye a nou vle ajoute yon pou riban isit la sa a, se ale nan repekte nan la klase, oswa rès la nan sa a etalaj. Nenpòt moun ki vle bay m 'yon liy nan kòd ki ta fè sa? Hint-- sa nou bezwen desann isit la? Ki sa ki k ap pase yo ale nan sa a pou riban? Yeah. ODYANS: Se konsa, nou ta vle gen yon nonb antye relatif diferan, paske nou ap kouri nan rès la nan etalaj la olye pou yo m nan, se konsa petèt j. 

Andi Peng: Yeah, j son bon m '. Pèr? 

ODYANS: Se konsa, ta dwe mwen plis 1, paske w ap kòmanse nan valè a kap vini an. Epi lè sa a end-- a pou ankò, j se mwens pase n mwens 1, ak Lè sa a j ++. Andi Peng: Great. 

Lè sa a, nan isit la, nou ap ale nan vle tcheke yo wè si se kondisyon nou an te rankontre, dwa? Paske ou vle chanje valè minimòm-nan si li la aktyèlman pi piti pase sa w ap konpare l 'bay, dwa? Se konsa, sa nou pral vle nan isit la? Tcheke yo wè. Ki kalite deklarasyon yo nou pwobableman pral ti vle sèvi ak si nou vle tcheke yon bagay? 

ODYANS: Yon si deklarasyon. 

Andi Peng: Yon si deklarasyon. Se konsa, if-- ak sa k ap pase yo dwe kondisyon an ke nou vle andedan a si deklarasyon nou an? 

ODYANS: Si valè a nan j se mwens pase valè a nan i-- 

Andi Peng: Egzakteman. Se konsa, if-- se konsa sa a etalaj yo rele "etalaj." Great. Se konsa, si sa ki te array-- sa? Di sa ankò. 

ODYANS: Si etalaj-j se mwens pase etalaj-mwen, lè sa a nou ta chanje min nan. Se konsa, min an ta dwe j. 

Andi Peng: Èske sans sa fè? OK. Epi, koulye a desann isit la, nou aktyèlman vle aplike swap a, dwa? Se konsa, sonje, nan konferans, David, lè li te ap eseye swap the-- sa ki te l-- ji zoranj ak milk-- 

ODYANS: Sa ki te brit. 

Andi Peng: Yeah, ki te kalite brit. Men, li te yon bon bèl konsèp demontre tan. Se konsa, panse nan valè ou isit la. Ou te gen yon etalaj a min, yon etalaj de mwen, oswa kèlkeswa sa nou t ap eseye swap isit la. Apre sa, pwobableman ou pa ka vide yo nan youn ak lòt an menm tan an, dwa? Se konsa, sa nou pral nan bezwen yo kreye isit la yo nan lòd yo swap valè yo kòrèkteman? 

ODYANS: Yon varyab tanporè. 

Andi Peng: Yon varyab tanporè. Se konsa, kite a fè int temp. Gade, sa a ta ka yon pi bon tan to-- ola, sa ki te sa? OK. Se konsa, sa ta gen yon pi bon tan nan non varyab "temp la." Se konsa, kite a fè int temp. Ki sa yo nou pral mete temp egal a isit la? ODYANS: Min? Andi Peng: Li se yon ti jan difisil. Li aktyèlman pa gen pwoblèm nan fen an. Li pa enpòtan ki sa lòd ou chwazi pou ou swap nan osi lontan ke w ap fè si w ap kenbe tras nan ki sa w ap échanjé. 

ODYANS: Li ta ka etalaj-mwen. 

Andi Peng: Yeah, kite a fè etalaj-mwen. Lè sa a, sa ki nan liy nan pwochen te nan kòd nou vle gen isit la? ODYANS: etalaj-mwen egal etalaj-j. Andi Peng: Epi anfen? ODYANS: etalaj-j egal etalaj-mwen. ODYANS: Ou etalaj-j egal etalaj-temp-- oswa, temp. 

Andi Peng: OK. Se konsa nou kouri sa a ak wè si li k ap pase nan travay. Ki kote se ke k ap pase? Oh, sa a, se yon pwoblèm. Gade, sou liy 40, nou ap ap eseye sèvi ak etalaj-j? Men, kote j sèlman egziste nan? 

ODYANS: Nan a pou riban. Andi Peng: Dwa. Se konsa, sa nou pral bezwen fè? 

ODYANS: Defini li an deyò the-- ODYANS: Yeah, mwen devine ou gen yo sèvi ak yon lòt si deklarasyon, dwa? Se konsa, tankou, si minimum-- nan tout dwa, kite m 'panse. 

Andi Peng: Guys, eseye pran yon gade Ann gade, sa k ap yon bagay nou kapab fè isit la? 

ODYANS: OK. Se konsa, si minimòm la fè sa ki pa egal j-- Se konsa, si minimòm la se toujou i-- lè sa a nou pa ta gen swap. 

Andi Peng: Èske sa egal mwen? Ki sa ou vle di la a? 

ODYANS: Ou yeah, si nan minimòm pa fè sa egal mwen, yeah. Andi Peng: OK. Oke ki rezoud, kalite, pwoblèm nou yo. Men, ki toujou pa rezoud nan pwoblèm nan sa k ap pase si j-- depi j pa egziste deyò nan li, ki sa ou nou vle fè ak li? Deklare li deyò a konsa? Ann eseye kouri sa a. Uh-oh. Sòt nou pa nan travay. 

Kòm ou ka wè, premye nou an etalaj te gen valè sa yo. Apre sa li ta dwe gen te nan 1, 2, 3, 4, 5, 6, 7, 8, 9. Li nan pa ap travay. Ahh. Ki sa nou fè? ODYANS: Debug. Andi Peng: Tout dwa, nou ka eseye sa. Nou ka debug. Rale soti yon ti jan. Se pou yo mete breakpoint nou an. Ann al like-- OK. 

Se konsa, paske nou deja konnen ke liy sa yo, 15 a 22, yo working-- paske tout m ap fè se jis iteration jiska ak nan printing-- Mwen ka ale pi devan epi sote sa. Ann kòmanse nan liy 25. Op, kite m 'debarase m de sa. 

ODYANS: Se konsa, breakpoint nan kote debogaj la kòmanse? Andi Peng: Ou arè. ODYANS: Ou arè. Andi Peng: Yeah. Ou ka mete plizyè breakpoints ak li ka jis vole soti nan yon nan lòt la. Men, nan ka sa a nou pa konnen kote erè a k ap pase. Se konsa, nou jis vle kòmanse soti nan tèt la desann. Oui. OK. 

Se konsa, liy sa a isit la, nou ka etap nan. Ou ka wè desann isit la, nou te gen yon etalaj. Moun sa yo se valè yo ki nan etalaj la. Ou wè ke, ki jan endèks 0, li koresponn ak value-- nan oh, Mwen pral pou yo eseye rale nan. Padon, li nan vrèman difisil see-- nan endèks etalaj 0, nou gen yon valè de 4 ak Lè sa a, pou fè ak sou sa. Nou gen varyab lokal nou yo. Dwa koulye a mwen ki egal a 0, ki nou vle li yo dwe. 

Se konsa, kite a kenbe kite nan. Minimòm nou se egal a 0, ki nou menm tou nou vle li yo dwe. Lè sa a, nou antre nan dezyèm nou an pou bouk, si etalaj-j se mwens pase etalaj-mwen, ki li pa t '. Se konsa, ou te wè ki jan ki sote sou sa? 

ODYANS: Se konsa, yo ta dwe a si minimòm, tout that-- pa ta dwe ki gen andedan premye a pou riban? Andi Peng: Non, paske ou toujou vle teste. Ou vle fè yon konparezon chak tan, menm apre ou kouri atravè li. Ou pa jis vle fè l ' sou premye pòsyon nan la. Ou vle fè l 'ak chak pas plis ankò. Se konsa, ou vle tcheke pou eta sante ou anndan an. Se konsa, nou ap jis ale nan kenbe kouri nan isit la. Mwen pral ba ou nèg yon allusion. Li te gen fè ak lefèt ke lè w ap tcheke kondisyonèl ou, ou pa ap tcheke pou endèks la kòrèk. Se konsa, kounye a ou ap tcheke pou endèks etalaj de j se mwens pase etalaj endèks nan m. Men, sa ki ou ap fè moute nan nan konmansman an nan la pou riban? Èske ou pa mete j egal a mwen? 

Yeah, se konsa nou kapab aktyèlman sòti debugjeur a isit la. Se konsa, kite a pran yon gade nan pseudocode nou an. Pou- nou ap ale nan kòmanse nan mwen egal 0. Nou pral moute al n mwens 1. Se pou yo tcheke, èske nou gen dwa sa? Oui, ki te gen rezon. 

Se sak fè andedan isit la, nou ap ale nan kreye yon valè minimòm , li mete ki egal a mwen. Èske nou fè sa? Oui, te fè sa. Koulye a, nan nou an anndan pou riban, nou ap pral fè j egal m 'n mwens 1. Èske nou fè sa? Vreman vre, nou te fè sa. 

Se konsa, sepandan, kisa nou konpare isit la? 

ODYANS: j plis 1. Andi Peng: Egzakteman. Lè sa a, w ap ale nan vle yo mete minimòm ou egal a j plis 1 kòm byen. Se konsa, mwen mache ale nan tout ki vrèman byen vit. Ou nèg konprann poukisa li a j plis 1? OK. 

Se konsa, nan etalaj ou a, nan pas premye ou a, ou pou riban, pou int mwen egal 0, kite yo jis asime sa a pa te chanje ankò. Nou gen yon etalaj de, konplètman, jis kat eleman klase, dwa? Se konsa, nou vle inisyalize mwen egal a 0. Apre sa, mwen ki pral jis kouri nan sa a riban. Se konsa, nan pas la premye, nou ap ale inisyalize yon varyab rele "min" ki tou egal mwen, paske nou pa gen yon valè minimòm. Se konsa, sa a, se kounye a egal a 0 kòm byen. Lè sa a, nou ap ale nan ale nan. E nou vle repekte ankò. Kounye a ke nou te jwenn sa minimòm nou an se, nou vle repekte nan ankò nan wè si li nan konpare, dwa? Se konsa, j, isit la, ki pral egal mwen, ki se 0. Lè sa a, si etalaj j plis mwen, ki se youn nan ki nan pwochen sou yo, kòm mwens pase sa ou ye kounye a minimòm valè, ou vle swap. 

Se konsa, kite yo jis di nou te te resevwa, tankou, 2, 5, 1, 8. Dwa koulye a, mwen ki egal a 0 ak j ki egal a 0. Epi sa a, valè minimòm nou an. Si etalaj-j plis i-- Se konsa, si yon sèl nan sa a, se apre yon nan nou ap chèche a gen plis pouvwa pase yon sèl la anvan li, li k ap pase yo vin minimòm la. 

Se konsa, isit nou wè ke 5 se pa mwens pase sa. Se konsa, li k ap pase pa yo dwe 5. Nou wè ke 1 se mwens pase 2, dwa? Se konsa, kounye a nou konnen ke minimòm nou an, se pral fè valè a endèks nan 0, 1, 2. Yeah? Lè sa a, lè ou jwenn desann isit la, ou ka swap valè yo kòrèk. 

Se konsa, lè ou nèg te jis gen j nan anvan, ou pa te gade nan yon sèl nan apre li fin. Ou te gade nan valè a menm, ki pou rezon sa li jis pa te fè anyen. Ki fè sans nan tout moun, poukisa nou bezwen ki plis 1 a? OK. Koulye a, kite yo jis kouri nan li fè asire w tout rès kòd la kòrèk. Poukisa se ke k ap pase? Ah, li nan min nan dwa isit la. Nou te konpare valè a sa ki mal. Oh pa gen okenn. 

Oh yeah, desann isit la nou te échanjé valè yo mal kòm byen. Paske nou te gade nan m ak j. Moun sa yo ki yo se yo menm nou te tcheke. Nou aktyèlman vle swap a minimòm, minimòm aktyèl la, ak tou sa deyò a se yon sèl. Ak jan ou nèg ka wè desann isit la, nou gen yon etalaj Ranje. Li jis te gen nan fè ak lefèt ke lè nou te tcheke nan valè nou te konpare, nou pa te gade nan valè yo dwat. Nou te gade nan yon sèl la menm isit la, pa aktyèlman échanjé li. Ou gen fè yon gade nan youn nan pwochen nan li ak Lè sa a ou ka swap. Se konsa, se sa ki te kalite bugging Kòd nou an anvan. Ak sa ki mwen te fè isit la se tout bagay debugjeur a te kapab te fè pou ou Mwen jis te fè li sou mòn lan tablo, paske li pi fasil wè olye ke ap eseye rale nan sou debugjeur a. Ki fè sans nan tout moun? Fre. 

Tout dwa. Nou ka deplase sou li nan ap pale de asenptotik notasyon, ki se jis yon fason anpenpan nan di a runtimes nan tout nan kalite sa yo. Se konsa, mwen konnen David, nan konferans, manyen sou runtimes. Apre sa, li mache ale nan tout fòmil la tout antye pou konnen kijan pou kalkile runtimes yo. Pa gen enkyetid sou sa. Si ou se reyèlman kirye sou kòman ki travay, santi yo lib pou pale ak m 'apre seksyon. Nou ka mache nan fòmil yo ansanm. Men, ou tout mesye gen reyèlman konnen se ke n okib plis pase 2 se menm bagay la kòm n okib. Paske nimewo a pi gwo, ekspozan an, ap grandi pi plis la. Se konsa, pou rezon nou an, tout sa nou pran swen sou se ke nimewo jeyan ki nan ap grandi. 

Se konsa, sa se ka a pi bon ègzekutabl nan sòt seleksyon? Si w ap ale nan gen repekte nan yon lis ak Lè sa a répétèr nan rès la nan ke lis, konbyen fwa yo ou menm ki pral pwobableman, nan case-- ki pi mal la nan la pi bon ka, sorry-- kouri nan? Petèt kesyon an pi bon se mande, ki sa ki ka ki pi mal ègzekutabl nan sòt seleksyon. ODYANS: n okib. Andi Peng: Li nan n okib, dwa. Se konsa, yon fason fasil yo panse a sa a se tankou, nenpòt ki lè ou gen de pare solèy pou pasan, li k ap pase yo dwe n okib. Paske pa sèlman moun ou ye kouri nan yon lòt fwa ankò, ou gen yo ale tounen ozalantou yo ak kouri atravè li yon lòt fwa ankò anndan pou chak valè. Se konsa, nan ka sa a, w ap kouri n fwa n okib, ki is-- regrèt, N fwa n, ki egal n okib. 

Ak sòt se tou yon ti jan inik nan sans ki li pa gen pwoblèm si sa yo valè yo deja nan lòd. Li nan toujou ale nan kouri nan aniwe. Se pou nou jis di sa a te 1, 2, 3, 4. Kèlkeswa si wi ou non li te nan lòd, li toujou ta gen kouri nan epi ou toujou ap tcheke valè a minimòm. Li ta te fè nan menm kantite chèk chak fwa yon sèl, menm si li pa t 'aktyèlman manyen anyen. 

Se konsa, nan ka sa a, pi bon an ak pi move runtimes yo aktyèlman ekivalan. Se konsa, ègzekutabl an te espere nan sòt seleksyon, nou pa deziyen senbòl la a Theta, Theta, nan ka sa a, ta tou gen pou n okib. Tout twa nan sa yo ta dwe n okib. Èske tout moun klè sou poukisa se ègzekutabl nan n okib? 

Tout dwa. Se konsa, mwen jis ale nan byen vit kouri nan rès la nan kalite yo. Algorithm a pou jarèt sort-- sonje, sa a te youn nan premye David janbe nan konferans. Esansyèlman, ou etap nan lis la tout antye epi ou swap-- ou jis konpare de nan yon tan. Men, si yon sèl nan pi gwo, pase ou jis swap yo. Se konsa, si sa yo, se pi gwo, ou ta swap. Mwen te gen ofisyèl dwa isit la. 

Se konsa, kite yo jis di ou te gen 8, 6, 4, 2. Ou ta konpare 8 la ak yon 6. Ou ta bezwen swap yo. Ou ta konpare 8 la ak yon 4. Ou ta bezwen swap yo. Si ou gen swap 8 la ak 2 a, chanje yo kòm byen. Se konsa, nan sa yo yon sans, ou ka wè, te jwe soti sou yon peryòd tan ki long, ki jan kalite a valè nan jarèt pwent yo, ki se poukisa nou rele li ti wonn sòt. 

Nou ta jis kouri nan ankò sou dezyèm pas nou an, ak twazyèm pas nou an, ak pas katriyèm nou an. Esansyèlman, ti wonn sòt jis kouri jiskaske ou pa fè okenn echanj plis. Se konsa, nan sans sa, sa a se jis pseudocode la an jeneral pou li. Pa gen enkyetid, sa yo pral tout ap sou entènèt. Nou pa gen aktyèlman ale sou sa a. 

Nou jis inisyalize yon vann san preskripsyon varyab ki kòmanse nan 0. Apre sa, nou repekte nan etalaj a tout antye. Men, si yon sèl valè is-- si sa a valè pi gwo pase sa valè, w ap ale nan swap yo. Lè sa a, ou se jis ale nan kenbe prale. Apre sa, w ap ale nan konte. Apre sa, w ap jis ale nan kontinye ap fè sa a pandan y ap vann san preskripsyon a gen plis pouvwa pase 0, ki vle di ke chak fwa ou gen swap, ou konnen ou vle ale retounen lakay yo epi tcheke ankò. Ou vle kenbe kont kouran jouk ou konnen ke ou pa gen swap ankò. 

Se konsa, sa se pi bon an ak pi move ka runtimes pou sòt jarèt? Apre sa, hint-- sa a se aktyèlman diferan soti nan sòt seleksyon nan sans ke de repons sa yo, se pa menm bagay la. Reflechi sou sa ki ka rive nan yon ka si li te deja klase. Epi reflechi sou sa ta rive si li te nan ka a nan ki li pa te Ranje. Epi ou ka kalite kouri a poukisa ki k ap pase. Mwen pral ba ou nèg, tankou, 30 segonn yo reflechi sou sa. 

OK. Nenpòt moun ki gen yon devine nan la sa pi move ègzekutabl ka ta gen sòt jarèt se? Yeah. 

ODYANS: li ta dwe, tankou, n fwa n mwens 1 oswa yon bagay tankou sa? Tankou, chak fwa li kouri, li nan jis, tankou, yon sèl swap mwens ki tou sa li te ye a. 

Andi Peng: Yeah, se konsa w ap totalman dwa. Lè sa a se yon ka nan ki ou repons te aktyèlman pi konplèks pase yon sèl la nou bezwen pou nou bay. Se konsa, li k ap pase yo run-- mwen se ale nan efase tout bagay sa a isit la. Èske tout moun sa ki bon? Èske mwen ka efase sa a? OK. W ap ale nan kouri nan n fwa premye fwa, dwa? Apre sa, yo ap ale nan kouri nan n mwens 1 dezyèm fwa, dwa? Lè sa a, w ap ale nan kenbe prale a, n m 2, et setra. David te fè sa a nan yon konferans, ki kote, si ou te ajoute moute tout moun sa yo valè, ou jwenn yon bagay sa a, se like-- yeah-- plis pase 2, ki esansyèlman jis diminye desann nan n okib. W ap ale nan jwenn yon etranj fraksyon nan la. Se konsa, jis konnen ke n nan okib toujou pran priyorite sou fraksyon. Se konsa, nan ka sa a, pi move a ta ègzekutabl dwe n okib. Si li te nan desann lòd, panse, ou gen fè yon swap chak fwa sèl. 

Ki sa ki ta dwe, potansyèlman, ègzekutabl a ka pi byen? Se pou nou jis di, si lis la te deja yo nan lòd, sa ki ta ègzekutabl nan ta dwe ye? 

ODYANS: n. Andi Peng: Se n, egzakteman. Epi poukisa se li n? ODYANS: Paske ou jis gen yo tcheke sou chak yon fwa. Andi Peng: Egzakteman. Se konsa, nan pi bon ègzekutabl ki posib, si lis sa a te deja sorted-- kite a di 1, 2, 3, 4-- ou ta jis ale nan, ou ta tcheke, ou ta wè, o, yo tout Pan deyò. Mwen pa t 'gen yo swap. Mwen fini. Se konsa, nan ka sa a, li nan jis n oswa nimewo a nan etap ou jis te gen yo tcheke nan lis la an premye. 

Apre yo te fin, kounye a nou frape sòt ensèsyon, kote algorithm nan se esansyèlman, fann li de l 'nan yon pòsyon Ranje ak triye. Lè sa a, youn pa youn, valè ki klase yo eleman nan ki apwopriye yo pozisyon nan nan konmansman an nan lis la. 

Se konsa, pou egzanp, nou gen yon lis 3, 5, 2, 6, 4 ankò. Nou konnen ke li nan kounye a triye paske nou te jis te kòmanse kap nan li. Nou pran yon gade e nou konnen ke se valè a premye Ranje, dwa? Si w ap sèlman gade nan yon etalaj de gwosè yon sèl, ou konnen ke li nan Ranje. 

Se sak fè nou konnen ke nan lòt kat yo triye. Nou ale nan ak nou wè ke valè. Se pou yo ale tounen. Wè ke valè de 5? Nou pran yon gade nan li. Nou konpare li a 3. Nou konnen ke li nan pi gran pase 3, se konsa nou konnen ke ki nan Ranje. Se konsa, nou konnen kounye a ke de nan premye yo ranje ak dènye twa a yo pa. 

Nou pran yon gade nan 2. Nou premye tcheke li ak 5. Èske li mwens pase 5? Se pa. Se konsa, nou gen kenbe kap desann. Lè sa a, ou tcheke 2 Off 3. Èske li mwens pase? No Se konsa, ou konnen yon 2 te pral figire nan devan an ak 3 ak 5 tou de gen yo dwe pouse soti. Fè sa ankò ak 6 ak 4. E nou jis kenbe tcheke esansyèlman, kote nou jis tcheke, tcheke, tcheke. Epi jouk li a nan bon an pozisyon, nou kalite jis insert l 'nan pozisyon an dwa, ki se kote non an nan li te soti nan. 

Se konsa, sa se sèlman algorithm a, pseudocode se pou chak, kalite, sou ki jan nou ta aplike yon sòt ensèsyon. Pseudocode se isit la. Li nan tout sou entènèt. Pa gen enkyetid si ou nèg yo se ap eseye kopi sa a desann. Se konsa, yon lòt fwa ankò, se li menm question-- sa ta dwe pi bon an ak pi move runtimes pou sòt ensèsyon? Li trè menm jan ak dènye kesyon an. Mwen pral ba ou nèg, tankou, 30 segonn yo reflechi sou sa a kòm byen. 

OK nenpòt moun vle ban m 'ègzekutabl ki pi mal la? Yeah. 

ODYANS: n okib. 

Andi Peng: Li nan n okib. Epi poukisa se li n okib? 

ODYANS: Paske nan ranvèse lòd, ou gen yo ale nan fwa n N, ki is-- Andi Peng: Yeah, egzakteman. Se konsa, menm bagay tankou nan sòt nan jarèt. Si sa a se nan lis desann lòd, w ap ale nan gen yo tcheke premye yon fwa. Lè sa a, ak tout plis valè, w ap ale nan gen yo tcheke li kont chak valè sèl, dwa? Se konsa, tout ansanm, w ap ale nan fè yon n pas fwa yon lòt n pase, ki se n okib. Ki sa ki sou ka a pi bon? Yeah. 

ODYANS: n mwens 1, paske nan premye yon sèl se deja au. 

Andi Peng: Se konsa, fèmen. Repons lan se aktyèlman n. Paske pandan y ap youn nan premye se Ranje, li pa gen dwa aktyèlman li nou jis lucked soti, nan ki egzanp, ke 2 te rive yo dwe nimewo nan pi piti a. Men, sa pa ap toujou gen ka-a. Si 2 se deja klase depi nan konmansman an men ou gade ak gen nan yon 1 isit la, 1 a pral frape li. Epi, se k ap pase nan fen ke yo te te fwape aniwe. 

Se konsa, nan senaryo a ka pi bon, li nan aktyèlman jis pral fè n. Si ou gen 1, 2, 3, 4, 5, 6, 7, 8, w ap ale nan kouri nan ke lis tout antye yon fwa tcheke yo wè si tout bagay amann lan. Èske tout moun klè sou kouri fwa nan seleksyon kòm byen? Mwen konnen mwen pral nan sa yo reyèlman vit. Men, jis konnen ke si ou konnen an konsèp jeneral, ou ta dwe bon. OK. Se konsa, mwen pral jis ba ou mesye petèt, tankou, yon minit pou pale ak vwazen ou sou sa ki yo se sèlman kèk nan diferans ki genyen prensipal ant sa yo kalite kalite. Nou pral ale sou ki byento. ODYANS: Oh, OK. Andi Peng: Yeah. OK. Cool, se pou yo reyini kòm yon klas la. OK. Se konsa, sa a te kalite yon kesyon tou louvri-te fini nan sans ke gen nan anpil nan repons yo. Epitou, n ap ale sou kèk nan yo yon ti tan. Mwen jis te vle jwenn ou nèg panse sou sa différenciés tout twa kalite kalite. Apre sa, mwen tande, tou, yon gwo question-- sa rantre sòt fè? Great kesyon, paske se sa sa n ap kouvri kap vini an. 

Se konsa, rantre sòt se nan youn sòt ki fonksyon trè diferan soti nan lòt kalite yo. Kòm ou nèg ka see-- David te fè sa Demo kote li te gen tout fre a bwi nan wè kijan rantre sòt kouri, tankou, enfiniman pi vit pase de lòt kalite yo? OK. Se konsa, sa a, se paske unifye sòt aplike ki divize ak konkeri konsèp ke nou te te pale osijè de yon anpil nan konferans. Nan sans sa ke nou renmen travay pi entelijan, pa pi rèd, lè ou divize ak konkeri pwoblèm, epi kraze yo desann, ak Lè sa a mete yo ansanm, bon bagay toujou rive. 

Se konsa, fason nan ki rantre sòt esansyèlman travay se ke li divize yon triye etalaj nan mwatye. Lè sa a, li nan te resevwa de mwatye nan ranje. Apre sa, li jis asòti moun de mwatye. Li jis kenbe divize an mwatye, nan mwatye, nan mwatye jouk tout bagay se Klase ak Lè sa a recursive mete l 'tout ansanm. 

Se konsa, sa ki nan vrèman abstrè. Se konsa, sa a se jis yon ti jan nan pseudocode. Ki fè sans nan wout la li nan kouri? Se konsa, kite yo jis di ou gen yon etalaj de eleman n, dwa? Si n se mwens pase 2, ou ka retounen. Paske ou konnen ke si gen nan sèlman yon sèl bagay, li dwe Ranje. Lòt Bagay, ou sòt mwatye nan bò gòch, ak Lè sa a ou sòt mwatye nan dwa, ak Lè sa a ou rantre. 

Se konsa, pandan ki sanble reyèlman fasil, an reyalite, panse sou li a kalite difisil. Paske w ap tankou, byen, ki nan kalite kouri sou tèt li. Dwa? Li nan kouri sou tèt li. Se konsa, nan sans sa, David manyen sou rkursyon nan klas la. Epi sa a, yon konsèp nou pral pale sou plis. Li nan ki sa a, de liy sa yo isit la, aktyèlman se jis pwogram nan di li nan dirije pwòp tèt li ak diferan opinyon. Se konsa, olye ke kouri tèt li ak antye a nan eleman n, ou ka kraze li desann nan la gòch mwatye ak mwatye nan dwa ak Lè sa a kouri l 'ankò. 

Lè sa a, nou pral gade nan li vizyèlman, paske mwen se yon elèv k ap aprann vizyèl. Li travay pi byen pou mwen. Se konsa, nou pral gade nan yon egzanp vizyèl isit la. 

Se pou nou di nou gen yon etalaj, sis eleman, 3, 5, 2, 6, 4, 1, pa Ranje. Tout dwa, gen nan yon anpil nan paj sa a. Se konsa, si ou nèg ka gade nan a Premye etap isit la, 3, 5, 2, 6, 4, 1, ou ka fann l 'nan mwatye. Ou gen 3, 5, 2, 6, 4, 1. Ou konnen ke sa yo aren't-- ou pa konnen si yo ap Ranje oswa ou pa, se konsa ou kenbe kraze yo desann, nan mwatye, nan mwatye, nan mwatye, jouk evantyèlman, ou sèlman gen yon sèl eleman. Epi se yon sèl eleman toujou Ranje, dwa? 

Se konsa, nou konnen ke 3, 5, 2, 4, 6, 1, pa tèt yo, yo ranje. Epi, koulye a nou ka mete yo tounen ansanm. Se konsa, nou konnen 3, 5 an. Nou mete moun ansanm. Nou konnen sa a, se Ranje. 2 nan yo toujou la. Nou ka mete 4 an ak 6 an ansanm. Nou konnen ke ki nan Ranje, se konsa nou mete sa ansanm. Ak 1 a ki gen la. 

Lè sa a, ou jis gade nan de mwatye sa yo dwa isit la. Ou gen 3, 5, 2, 2, 3, 5 an. Ou ka jis konpare a kòmanse nan tout bagay. Paske ou konnen ke sa a se Klase epi ou konnen ke ki nan Ranje. Se konsa, lè sa a ou pa menm gen yo konpare a 5, ou jis konpare 3 an. Ak 2 a se mwens pase 3, se konsa ou konnen 2 dwe ale nan fen an. 

Menm bagay sou la. 1 a dwe ale isit la. Lè sa a, lè ou ale nan mete de valè sa yo ansanm, ou konnen ke sa a se klase epi ou konnen ke ke se Ranje. Se sak fè ak an a 1 2, 1 a se mwens pase 2. Ki di ou ke 1 an ta dwe ale sou fen a nan sa a san yo pa menm gade nan 3 oswa 5. Lè sa a, 4 an, ou ka jis tcheke, li ale dwat nan isit la. Ou pa gen fè yon gade nan 5 an. Menm bagay ak 6 an. Ou konnen ke li jis nan 6-- pa bezwen gade. 

Se konsa, nan fason sa a, w ap jis ekonomize tèt ou yon anpil nan etap lè w ap konpare. Ou pa gen yo konpare chak eleman kont lòt eleman. Ou jis konpare kont yo menm ki ke ou bezwen konpare li kont. Se konsa, sa a, se kalite yon konsèp abstrè. Pa gen enkyetid si li pa byen frape ou dwa ankò. Men, jeneralman, sa a se ki jan yon sòt unifye fonksyone. Kesyon, kesyon rapid, anvan m 'deplase sou? Yeah. 

ODYANS: Se konsa, ou te di ke ou pran 1 an, ak Lè sa a 4 an, ak 6 nan li mete yo nan. Se konsa, yo pa those-- yo pa ou ap chache nan yo kòm eleman ki apa a, pa tankou tout la? Andi Peng: Yeah. Se konsa, sa k ap pase se ke ou fondamantalman ap kreye yon mak nouvo etalaj. Se konsa, ou konnen ke, isit la, mwen gen de ranje nan gwosè 3, dwa? Se konsa, ou konnen ke etalaj Ranje mwen bezwen gen sis eleman. Se konsa, ou jis kreye yon nouvo kantite lajan pou memwa. Se konsa, ou ap kalite tankou ke yo te inutil nan memwa, men sa pa gen pwoblèm paske li nan konsa ti. Se konsa, ou gade nan 1 a epi ou gade nan 2 a. E ou konnen ke 1 a se mwens pase 2. Se konsa, ou konnen ke 1 ta dwe ale nan nan konmansman an nan tout nan sa yo. 

Ou pa menm bezwen gade nan 3 an ak 5 an. Se konsa, ou konnen 1 ale la. Lè sa a, ou fondamantalman koupe koupe 1 an. Li nan, tankou, mouri yo ban nou. Lè sa a, nou jis gen 2, 3, 5, ak Lè sa a 4 ak 6. Lè sa a, ou konnen sa, ou konpare 4 an ak 2 a, oh, 2 a ta dwe antre nan peyi a. Se konsa, ou plok desann nan 2, ou koupe l 'la. Se sak fè ou jis gen 3 nan ak 5 an nan 4 an ak 6 an. Epi ou jis kenbe découper li koupe jiskaske ou mete yo nan etalaj la. 

ODYANS: Se konsa, ou ap jis toujou konpare [fèbl a]? 

Andi Peng: Egzakteman. Se konsa, nan sans sa, w ap jis konpare, esansyèlman, yon sèl nimewo kont lòt nimewo a. Epi paske ou konnen ke li nan Ranje, ou pa bezwen gade nan tout nan nimewo yo. Ou jis gen gade nan yon sèl la an premye. Lè sa a, ou ka jis plok yo desann, paske ou konnen yo apatni kote yo bezwen fè pati. Yeah. Bon kesyon. 

Lè sa a, si yon moun pami nou se yon ti jan anbisye, santi yo lib fè yon gade nan Kòd sa a. Sa a se aktyèlman nan aplikasyon fizik nan ki jan nou ta ekri sòt unifye. Epi ou ka wè, li nan trè kout. Men, lide yo dèyè li yo trè konplèks. Se konsa, si ou santi ou tankou desen sa a soti nan aswè a devwa ou, santi yo lib yo. 

OK. Se konsa, David te janbe lòt sa a nan konferans. Ki sa ki ka ki pi bon runtimes, pi move runtimes ka, ak runtimes yo atann nan sòt unifye? Yon koup segonn yo panse. Sa a se trè difisil, men kalite entwisyon si ou panse sou li. Tout dwa. 

ODYANS: Èske pi move ka n boutèy demi lit n nan? Andi Peng: Egzakteman. Epi poukisa se li n boutèy demi lit n. 

ODYANS: Se pa li paske li vin exponentielle pi vit, se konsa li a tankou yon fonksyon nan ki olye pou yo jis tou senpleman ke yo te n okib oswa yon bagay? Andi Peng: Egzakteman. Se konsa, rezon an pou kisa nan ègzekutabl sou sa a se boutèy demi lit n n se because-- ki sa yo ou fè nan tout nan etap sa yo? Ou ap jis découper l 'nan mwatye, dwa? Se konsa, lè nou ap fè nan ouvri sesyon yo, tout ke li nan fè se divize yon pwoblèm nan mwatye, nan mwatye, nan mwatye, nan plis mwatye. Ak nan sans sa, ou kapab kalite a elimine modèl la lineyè ke nou ve yo te lè l sèvi avèk. Paske lè ou koupe bagay sa yo nan mwatye, li nan yon boutèy demi lit. Se jis nan matematik fason pou reprezante li. 

Lè sa a, finalman, nan fen a, w ap jis fè yon sèl pas dènye a yo mete tout nan yo yo nan lòd, dwa? Se konsa, si ou jis gen nan tcheke yon sèl bagay, sa a, se n. Se konsa, w ap kalite miltipliye ansanm nan de. Se konsa, li la tankou ou te gen ki final tcheke pou n desann isit la ak yon boutèy demi lit plen n moute isit la. Men, si ou anpil anpil pitit yo, ki nan n boutèy demi lit n. 

Se konsa, ka ki pi bon ak pi move ka e te espere yo tout n boutèy demi lit n. Li la tou tankou yon lòt sòt. Se tankou sòt seleksyon nan sans ke li pa gen pwoblèm sa ou lis sa ki, li nan jis ale fè menm bagay la chak fwa sèl. OK. Se konsa, kòm ou nèg ka wè, menm si kalite sa yo ke nou te ale through-- N okib, li nan pa trè efikas. E menm sa a boutèy demi lit n se n pa pi efikas la. Si ou nèg yo se kirye, gen nan fòmil sòt ki yo, se pou efikas ke yo ap prèske esansyèlman plat nan ègzekutabl. 

Ou te gen kèk boutèy demi lit n nan. Ou te gen kèk boutèy demi lit boutèy demi lit n nan. Nou pa manyen sou yo nan klas sa a kounye a. Men, si ou nèg yo se kirye, santi yo lib yo google, sa ki nan pi efikas klasman fòmil yo. Mwen pa konnen, gen kèk moun reyèlman komik, like-- gen nan kèk vrèman yo menm komik ki moun ki fè. Epi ou mande ki jan yo tout tan tout tan te panse de sa. Se konsa, Google, si ou gen kèk rezèv tan, sou li a, ki sa yo kèk fason komik ki people-- osi byen ke efikas moun ways-- te kapab aplike kalite. OK. Ak isit la nan jis yon sou la men ti kras tablo. Mwen konnen tout moun nan nou la a, anvan sa egzamen 0, yo pral nan chanm ou pwobableman ap yo memorize sa. Se konsa, sa a, se bèl nan gen pou ou guys. Jis pa bliye lojik nan ki made-- poukisa moun ki nimewo yo te rive. Si w ap toujou pèdi, jis fè w ke ou konnen ki sa kalite yo ye. Epi ou ka kouri nan yo nan lide ou eseye figi konnen poukisa moun repons moun sa yo ki repons. 

Tout dwa. Se konsa, nou ap ale pou avanse pou pi sou li a, finalman, nan chache. Paske kòm moun nan nou ki te li pset a, chache se tou yon pati nan pwoblèm yo semenn sa a kouche. Ou pral mande yo aplike de kalite rechèch. Youn nan se yon rechèch lineyè ak se yon sèl yon rechèch binè. 

Se konsa, rechèch la lineyè se jistis fasil. Ou jis vle fè rechèch eleman nan yon lis yo wè si ou jwenn li. Ou jis bezwen repekte nan. Men, si li egal yon bagay, ou ka jis retounen li, dwa? Men, yon sèl la ki nou ap pi enterese nan ap pale de se rechèch binè, dwa, ki se nan divize ak konkeri mekanis ki David te demontre nan konferans. 

Sonje egzanp lan liv telefòn ke li kenbe pote moute, yon sèl la ke li kalite plede yon ti jan sou ane sa a sot pase yo, kote ou divize pwoblèm lan nan mwatye, nan mwatye, nan mwatye, ankò e ankò, jiskaske ou jwenn sa w ap chèche pou? Apre sa, ou te gen a ègzekutabl nan ki kòm byen. Epi ou ka wè, li nan siyifikativman pi efikas pase nenpòt lòt kalite rechèch. 

Se konsa, wout la ke nou ta ale sou mete ann aplikasyon yon rechèch binè se, si nou te gen yon etalaj, endèks 0 a 6, sèt eleman, nou ka gade nan mitan an, regleman regrèt, si kesyon nou first-- si nou vle mande kesyon an nan, èske etalaj la gen eleman nan, 7, evidamman, yo te moun, epi ki gen tankou yon etalaj piti, li fasil pou nou yo di wi. Men, wout la nan aplike yon binè rechèch ta dwe fè yon gade nan mitan yo. 

Nou konnen ke endèks 3 se mitan an, paske nou konnen gen sèt eleman. Ki sa ki 7 divize pa 2? Ou ka koupe koupe ki siplemantè 1. Ou te gen 3 nan mitan yo. Se konsa, se etalaj de 3 egal a 7? Li se pa, dwa? Men, nou ka fè yon koup nan chèk yo. Èske etalaj de 3 mwens pase 7 oswa se etalaj de 3 pi gran pase 7? 

E nou konnen ke li nan mwens pase 7. Se konsa, nou konnen ke, o, li dwe Ou pa bezwen nan mwatye a gòch. Nou konnen ke li dwe nan mwatye nan dwa, dwa? Se konsa, nou ka jis koupe koupe mwatye etalaj la. Nou pa menm gen gade nan li ankò. Paske nou konnen ke mwatye nan nou an problem-- nou konnen ke repons la se nan mwatye nan dwa nan pwoblèm nou yo. Se konsa, nou jis gade nan ki kounye a. 

Se konsa, kounye a nou gade nan presegondè nan sa ki rete. Sa endèks 5. Nou fè menm bagay la ankò chèk epi nou wè ke li nan pi piti. Se konsa, nou gade sou bò goch la nan sa. Lè sa a, nou wè ke chèk la. Se valè a etalaj nan endèks 4 egal a 7? Li ye. Se konsa, nou ka retounen vre, paske nou jwenn valè a nan lis nou an. Èske wout la mwen te ale nan ki fè sans nan tout moun? OK. Mwen pral ba ou nèg petèt, tankou, twa, kat minit eseye figi konnen Ki jan yo pseudocode sa a nan. 

Se konsa, imajine Mwen te mande ou yo ekri yon fonksyon rele search () ki tounen se yon valè, se yon valè Boolean, sa ki te vre oubyen false-- tankou, vre si ou te jwenn nan valè, fo si ou pa t '. Lè sa a, ou te pase nan valè a ou te kap chèche nan valè, ki se array-- nan oh, mwen definitivman mete ke an plas an mal. OK. Aniwe, ki ta dwe gen te a dwat a valè. Lè sa a, int n se nimewo a nan eleman nan ki etalaj. Kouman ou ta ale sou ap eseye pseudocode ke pwoblèm nan? Mwen pral ba ou nèg tankou twa minit fè sa. Non, mwen panse ke gen nan only-- yeah, gen nan yon sèl dwa moute isit la. ODYANS: Èske mwen ka? Andi Peng: Yeah, mwen te resevwa ou. Eske se sa ke k ap travay? OK, fre. 

OK. Tout mesye dwat, nou ap ale nan rein li nan. OK. Se konsa, asime nou te gen sa a bèl ti kras etalaj ak valè N ladan l '. Mwen pa t 'trase liy yo. Men, ki jan nou ta ale sou ap eseye ekri sa a? Nenpòt moun ki vle ban m 'liy lan premye? Si ou vle bay nan m ' premye liy nan pseudocode sa a. 

ODYANS: [fèbl] ODYANS: Ou ta vle repekte nan ODYANS: Jis yon lòt pou riban? ODYANS: --for. 

Andi Peng: Se konsa, yon sèl sa a nan yon ti jan difisil. Panse sou- ou vle kenbe kouri sa a riban sou yo ak sou ankò jouk lè? 

ODYANS: Jiska [fèbl a] valè egal ak sa yo ki valè. Andi Peng: Egzakteman. Se konsa, ou ka aktyèlman jis write-- nou ka menm senplifye li plis. Nou ka jis fè yon riban pandan y ap, dwa? Se konsa, ou ka jis gen loop-- nou konnen ke li nan yon ti tan. Men, pou kounye a, mwen pral yo di "riban" - nan ki sa? Loop until-- ki sa ki kondisyon k ap fini nou an? Mwen panse ke m 'te tande l'. Mwen tande yon moun di li. 

ODYANS: Valè egal presegondè. Andi Peng: Di l 'ankò. ODYANS: Ou, jouk nan valè w ap chèche pou ki egal a valè a presegondè. 

Andi Peng: E ​​si li pa nan genyen? E si valè a w ap chèche pou se pa aktyèlman nan etalaj sa a? ODYANS: Ou retounen 1. 

Andi Peng: Men, ki sa nou vle bouk jouk si nou gen yon kondisyon? Yeah. 

ODYANS: Jiska gen nan sèlman yon sèl valè? Andi Peng: Ou kapab bouk until-- pou w konnen ke w ap pral gen yon valè max, dwa? Epi ou konnen ke w ap ale gen yon valè min, dwa? Paske tou, sa a, se yon bagay Mwen bliye yo di anvan, ke yon bagay sa a, se kritik sou rechèch binè se ke se etalaj ou deja klase. Paske gen nan pa gen fason pou fè sa a si yo ap valè jis o aza. Ou pa konnen si yon sèl nan pi gwo pase lòt la, dwa? 

Se konsa, ou konnen ke ou ak max mn ou la a, dwa? Si w ap ale yo dwe ajiste max ou nan mn ou ak mid-- yo kite yo jis asime ou mitan valè dwat isit lan-- w ap ale nan fondamantalman bouk jouk minimòm ou a se sou menm jan ak max ou, dwa, oswa si max ou a pa menm bagay la kòm min ou yo. Dwa? Paske lè sa rive, ou konnen ke ou te evantyèlman frape valè a menm. Se konsa, ou vle riban jiskaske min ou se mwens pase oswa egal to-- Wouch, pa mwens pase oswa egal a, nan lòt fason around-- max se. 

Èske ki fè sans? Mwen te pran yon eseye kèk jwenn ki dwat. Men, bouk jouk valè max ou se esansyèlman prèske mwens pase oswa egal a minimòm ou, dwa? Sa a lè ou konnen ke ou te convergé. ODYANS: Lè ta maksimòm ou valè dwe mwens pase minimòm nan? Andi Peng: Si ou kenbe ajiste li, ki se sa nou pral yo dwe fè nan sa a. Ki fè sans? Minimòm ak max yo se jis nonm antye relatif ke nou yo se pwobableman ale nan vle kreye kenbe tras nan kote nou ap chèche. Paske etalaj la egziste kèlkeswa sa n ap fè. Tankou, nou pa ap aktyèlman fizikman découper koupe etalaj la, dwa? Nou jis ap ajiste kote nou ap chèche. Ki fè sans? 

ODYANS: Yeah. 

Andi Peng: OK. Se konsa, si sa a, se kondisyon an pou riban nou an, ki sa nou vle andedan nan sa a riban? Ki sa yo nou pral yo dwe vle fè? Se konsa, kounye a, nou te gen yon max ak yon min, dwa, pwobableman kreye moute isit la yon kote. Nou pral pwobableman vle jwenn yon mwayen, dwa? Kouman yo nou pral fè kapab jwenn mitan an? Ki sa ki nan nan mathematical-- ODYANS: Max plis min divize pa 2. Andi Peng: Egzakteman. Ki fè sans? Apre sa, ou nèg wè poukisa nou pa t 'jis use-- poutèt sa nou te fè sa olye pou yo jis ap fè n divize pa 2? Li nan paske n se yon valè ki k ap pase yo rete menm bagay la. Dwa? Men, kòm nou ajiste minimòm nou yo ak valè maksimòm, yo pwal santi yo chanje. E kòm yon rezilta, mwayen nou ki pral chanje tou. Se konsa, Se poutèt sa nou vle fè dwa sa-a isit la. OK. 

Lè sa a,, kounye a ke nou te jwenn our-- yeah. 

ODYANS: Jis yon question-- rapid lè ou di min ak max, yo nou an konsideran ke li nan deja klase? 

Andi Peng: Yeah, sa a, se aktyèlman yon kondisyone pou yon rechèch binè, ki di ou gen konnen li la Ranje. Ki se poukisa sòt, ou ekri nan ou pwoblèm mete devan rechèch binè ou yo. OK. Se konsa, kounye a ke nou konnen ki kote pwen milye nou an se, ki sa ou vle fè isit la? 

ODYANS: Nou vle yo konpare ki nan yon sèl la ak lòt. Andi Peng: Egzakteman. Se konsa, w ap ale nan konpare mitan nan valè, dwa? Ak sa ki ki di nou lè nou konpare? Ki sa nou vle fè apre sa? 

ODYANS: Si valè a se pi gwo pase nan mitan yo, nou vle koupe l 'la. Andi Peng: Egzakteman. Se konsa, si valè a se pi gwo pase mitan, nou ap ale nan vle chanje sa yo minimòm ak Maxes, dwa? Ki sa nou vle chanje? Se konsa, si nou konnen valè a se yon kote nan isit la, sa ki fè ou nou chanje? Nou vle chanje nou an minimòm yo dwe mitan, dwa? Lè sa a, lòt bagay, si li nan nan sa a mwatye, ki sa nou vle chanje? 

ODYANS: maksimòm ou. Andi Peng: Yeah. Lè sa a, w ap jis ale kenbe loupin, dwa? Paske kounye a, apre yo fin yon sèl iterasyon nan, ou te gen yon max isit la. Lè sa a, ou ka rkalkulra yon mitan. Lè sa a, ou ka konpare. Apre sa, w ap ale nan kenbe prale jouk mn yo ak Maxes yo te esansyèlman convergé. Epi sa a, lè ou konnen ke ou te frape nan fen li. Apre sa, swa ou te jwenn li oswa ou pa gen nan pwen sa a. 

Sa a fè sans nan tout moun? OK. Sa a se trè enpòtan, paske ou pral gen yo ekri sa a nan aswè a kòd ou a. Men, ou nèg gen yon trè bon sans de ki sa ou ta dwe ap fè, ki se bon. OK. Se konsa, nou te gen sou sèt minit kite seksyon. Se konsa, nou ap ale nan pale sou pset sa a ke nou pral fè. Se konsa, se pset a divize an de mwatye. Mwatye nan premye enplike nan mete ann aplikasyon yon jwenn nan kote ou ekri yon rechèch lineyè, se yon rechèch binè, ak yon algorithm klasman. 

Se konsa, sa a se premye nan tan nan yon pset kote nou pral bay ou nèg sa ki rele Kòd distribisyon, ki se kòd ke nou te pre-ekri, men jis kite kèk moso koupe pou ou pou w fini ekri. Se konsa, ou nèg, lè ou gade nan sa a Kòd, ou ta ka jwenn reyèlman pè. Si w ap jis renmen, ahh, mwen pa konnen ki sa ki nan ap fè travay, Mwen pa konnen, tankou, ki sanble se konsa konplike, ahh, rilaks. Li nan OK. Li espèk a. Espèk a ap esplike ou egzakteman sa ki tout nan pwogram sa yo ap fè a. 

Pou egzanp, generate.c se yon pwogram ki pral vini ak pset ou yo. Ou pa gen aktyèlman manyen li, men li ou ta dwe konprann ki sa li la fè a. Apre sa, generate.c, tout li a fè se swa génération nimewo o aza oswa ou ka bay li yon pitit pitit, tankou yon Nimewo planifye davans ke li pran, epi li jenere plis chif yo. Se konsa, gen nan yon fason espesifik nan aplike generate.c nan ki ou ka jis fè yon pakèt moun sou nimewo pou ou pou w teste lòt metòd ou sou. 

Se konsa, si ou te vle, pou egzanp, tès jwenn ou, ou ta vle kouri generate.c, jenere yon pakèt moun sou nimewo, ak Lè sa a kouri fonksyon moun k'ap ede ou yo. Fonksyon moun k'ap ede ou se kote w ap aktyèlman fizikman ekri kòd. Apre sa, panse a moun k'ap ede kòm yon dosye bibliyotèk w ap ekri ki jwenn ap rele. Se konsa, ki nan helpers.c, ou pral fè chache ak klasman. 

Lè sa a, w ap ale nan esansyèlman jis mete yo tout ansanm. Espèk a ap di ou ki jan yo mete sa sou liy lan lòd. Men, ou pral kapab teste si wi ou pa sòt ou ak rechèch ap travay. Fre. Èske nenpòt moun ki deja kòmanse ak pwoblèm rankontre oswa kesyon yo gen dwa kounye a ak sa a? OK. 

ODYANS: Rete tann. Mwen gen yon kesyon. 

Andi Peng: Yeah. 

ODYANS: Se konsa, mwen te kòmanse fè rechèch la lineyè nan helpers.c epi li pa te vrèman ap travay. Men, Lè sa pita, mwen te jwenn deyò nou jis gen efase li epi fè binè rechèch. Se konsa, li enpòtan si li pa travay? 

Andi Peng: Kout repons se non. Men, depi nou ap not-- ODYANS: Men, yonn pa gen okenn nan aktyèlman tcheke. Andi Peng: Nou ap pa janm pral wè sa. Men, pwobableman ou vle fè asire w rechèch ou ap travay. Paske si ou lineyè rechèch pa travay, Lè sa a, chans yo se ou binè rechèch se pa sa ale nan travay kòm byen. Paske ou gen menm jan an lojik nan tou de peyi yo. E pa gen, li pa reyèlman gen pwoblèm. Se konsa, yo menm sèlman ou pral vire nan yo se sòt ak rechèch binè. Yeah. 

Epi tou, yon anpil nan timoun yo te ap eseye konpile helpers.c. Ou pa ap aktyèlman pèmèt fè sa, paske helpers.c pa gen yon fonksyon prensipal la. Se konsa, ou ta dwe sèlman gen aktyèlman konpile jenere epi jwenn, paske jwenn apèl helpers.c ak fonksyon yo nan li. Se konsa, ki fè debogaj yon doulè nan bou la. Men, sa a ki sa nou dwe fè. ODYANS: Ou jis fè tout, dwa? Andi Peng: Ou ka jis fè tout kòm byen, yeah. OK. Se konsa, sa a, se li an tèm de ki sa pset a ap mande nou tout fè. Si w gen nenpòt kesyon, santi lib yo mande m 'apre seksyon. Mwen pral dwe isit la pou li a, tankou, 20 minit. 

Apre sa, yeah, pset yo nan reyèlman pa sa ki move. Ou nèg yo ta dwe OK. Sa yo, jis swiv direktiv. Kalite gen yon sans de, lojikman, ki sa Yo ta dwe vini epi ou pral amann. Ou pa bezwen twò pè. Genyen yon anpil nan kòd deja ekri la. Ou pa bezwen twò pè si ou pa fè sa konprann sa nan tout sa vle di. Si li nan yon anpil, li nan totalman amann. Ak vini nan lè biwo. Nou pral ede w pran yon gade. 

ODYANS: Avèk siplemantè a fonksyon, nou gade moun a? 

Andi Peng: Yeah, sa yo se nan kòd la. Nan jwèt la nan 15, mwatye nan li nan deja ekri pou ou. Se konsa, moun yo fonksyon deja nan kòd la. Oui. Tout dwa. Oke, pi bon an chans. Li se yon jou degoutan. Se konsa, èspere ke ou nèg pa santi twò move sou rete andedan ak kodaj.