Doug Lloyd: Se konsa, nan CS50, nou te kouvri yon anpil nan estrikti done diferan, dwa? Nou te wÃ¨ ranje, ak lye lis, ak tablo yo regle, ak ap eseye, pil ak ke moun kap kriye. Nou pral aprann tou yon ti kras sou pye bwa ak pil, men vrÃ¨man sa yo tout jis fini ke yo te varyasyon sou yon tÃ¨m. Gen reyÃ¨lman yo sa yo kalite kat lide debaz ke tout bagay lÃ²t moun ka bouyi desann nan. Ranje, lis lye, tab regle, ak ap eseye. Li te tankou m 'te di, gen se varyasyon sou yo, men sa a se trÃ¨ pi ale nan rezime tout sa nou ap ale nan pale sou nan klas sa a an tÃ¨m de C. Men, ki jan fÃ¨ sa yo tout mezi moute, dwa? Nou te te pale osijÃ¨ de avantaj yo ak dezavantaj nan chak nan videyo separe sou yo, men gen nan yon anpil nan nimewo ap resevwa jete alantou. Genyen yon anpil nan jeneral panse ap resevwa jete alantou. Ann eseye ak konsolide l 'nan jis yon sÃ¨l kote. Se pou yo peze avantaj yo kont enkonvenyans yo, epi konsidere ki estrikti done ta ka done yo dwat estrikti pou sitiyasyon an patikilye ou a, tou sa kalite done w ap estoke. Ou pa nesesÃ¨man toujou bezwen itilize Super vit ensÃ¨syon, sipresyon an, ak Passage nan yon trye si ou reyÃ¨lman pa pran swen sou mete ak efase twop. Si ou bezwen jis byen vit o aza aksÃ¨, petÃ¨t yon etalaj se pi bon. Se konsa nou distile sa. Se pou nou pale sou chak nan kat la kalite pi gwo nan estrikti done ke nou te pale osijÃ¨ de, ak jis wÃ¨ yo lÃ¨ yo ta kapab bon, ak yo lÃ¨ yo pa ta ka tÃ¨lman bon. Se konsa, kite la kÃ²manse avÃ¨k ranje. Se konsa, ensÃ¨syon, ki nan kalite move. 

EnsÃ¨syon nan fen yon etalaj se OK, si nou ap bati yon etalaj jan nou ale. Men, si nou bezwen insert eleman nan mitan an, panse tounen nan ensÃ¨syon sÃ²t, gen nan yon anpil a dÃ©placement nan anfÃ²m yon eleman nan la. Se konsa, si nou ap ale nan Insert nenpÃ²t kote, men nan fen yon etalaj, sa a, se pwobableman pa konsa pou sa gwo. 

Menm jan tou, sipresyon, sof si nou ap efase soti nan nan fen yon etalaj, se pwobableman tou pa konsa pou sa gwo si nou pa vle kite twou vid ki genyen vid, ki se nÃ²malman nou pa fÃ¨ sa. Nou vle yo retire yon eleman, ak LÃ¨ sa a, sÃ²t de fÃ¨ li confortable ankÃ². Se konsa, efase eleman soti nan yon etalaj, tou pa tÃ¨lman gwo. 

Passage, menm si, se gwo. Nou gen aksÃ¨ o aza, konstan tan Passage. Nou jis di sÃ¨t, epi nou ale nan etalaj demenajman sÃ¨t. Nou di 20, ak ale nan etalaj demenajman 20. Nou pa bezwen repekte nan tout. Sa a trÃ¨ bon. 

Ranje yo tou relativman fasil sÃ²t. Chak fwa nou te pale de yon klasman algorithm, tankou sÃ²t seleksyon, sÃ²t ensÃ¨syon, sÃ²t jarÃ¨t, rantre sÃ²t, nou toujou itilize ranje fÃ¨ li, paske ranje yo trÃ¨ fasil yo sÃ²t, relatif nan estrikti yo done nou te wÃ¨ byen lwen tÃ¨lman. 

Yo ap tou relativman ti. Gen nan pa yon anpil nan espas siplemantÃ¨. Ou jis mete sou kote egzakteman kÃ²m anpil jan ou bezwen kenbe done ou a, e ke sa a bÃ¨l anpil li. Se konsa, yo ap trÃ¨ ti ak efikas nan fason sa a. Men, yon lÃ²t inconvÃ©nient, menm si, se yo ke yo yo se fiks nan gwosÃ¨. Nou gen deklare egzakteman ki jan gwo nou vle etalaj nou an yo dwe, epi nou sÃ¨lman jwenn yon sÃ¨l piki nan li. Nou pa ka grandi ak retresi li. 

Si nou bezwen yo grandi oswa retresi li, nou bezwen deklare yon etalaj totalman nouvo, kopi tout nan eleman ki nan la premye etalaj nan etalaj la dezyÃ¨m fwa. Men, si nou miscalculated ki tan, nou bezwen fÃ¨ l 'ankÃ². Pa tÃ¨lman gwo. Se konsa, ranje pa ban nou fleksibilite nan gen nimewo varyab nan eleman. 

AvÃ¨k yon lis lye, ensÃ¨syon se trÃ¨ fasil. Nou jis fofile sou devan an. Sipresyon se tou trÃ¨ fasil. Nou gen jwenn eleman yo. Sa enplike kÃ¨k rechÃ¨ch. 

Men, yon fwa ou te jwenn eleman nan w ap chÃ¨che pou yo, tout sa ou bezwen fÃ¨ se chanje yon konsÃ¨y, pÃ¨tÃ¨t de si ou gen yon lye list-- yon doubl lis lye, rather-- ak LÃ¨ sa a ou ka jis libere ne la. Ou pa gen chanjman tout bagay alantou. Ou jis chanje de endikasyon, se konsa ke a trÃ¨ rapid. 

Passage se move menm si, dwa? Yo nan lÃ²d pou nou pou n jwenn yon eleman nan yon lis lye, si wi ou non separeman oubyen doubl lye, nou dwe lineyÃ¨ rechÃ¨ch li. Nou dwe kÃ²manse nan kÃ²mansman an ak deplase fen a, oswa kÃ²manse nan fen mouvman an nan konmansman an. Nou pa gen aksÃ¨ o aza ankÃ². Se konsa, si n ap fÃ¨ yon anpil nan rechÃ¨ch, petÃ¨t yon lis lye se pa byen tÃ¨lman bon pou nou. 

Yo ap tou vrÃ¨man difisil a sÃ²t, dwa? SÃ¨l fason pou ou kapab reyÃ¨lman sÃ²t yon lis lye se yo sÃ²t li jan ou konstwi li. Men, si ou sÃ²t li jan ou konstwi li, ou ap pa gen okenn ankÃ² fÃ¨ parusyon rapid ankÃ². W ap pa sÃ¨lman tacking bagay sou devan an. Ou gen jwenn nan plas dwa mete l ', ak LÃ¨ sa a ensÃ¨syon ou vin jis sou tankou move kÃ²m mete nan yon etalaj. Se konsa, lis lye yo pa tÃ¨lman gwo pou klasman done. 

Yo ap tou trÃ¨ piti, gwosÃ¨-gen bon konprann. Doubl lye lis yon ti kras pi gwo pase lis separeman lye, ki se ti kras pi gwo pase ranje, men li la pa yon kantite lajan gwo gaspiye espas. Se konsa, si espas se nan yon prim, men pa yon prim reyÃ¨lman entans, sa a ta kapab yon dwa chemen yo ale. 

Tab regle. EnsÃ¨syon nan yon tab regle se jistis senp. Li se yon pwosesis de-etap. Premye nou bezwen kouri done nou yo atravÃ¨ yon fonksyon regle yo ka resevwa yon kÃ²d hash, ak LÃ¨ sa a nou Insert eleman an nan la regle tab nan ki kote KÃ²d regle. 

Sipresyon, menm jan ak lis lye, se fasil yon fwa ou jwenn eleman an. Ou gen jwenn li an premye, men LÃ¨ sa a lÃ¨ ou efase li, ou jis bezwen fÃ¨ echanj yon koup la endikasyon, si w ap itilize AnchÃ¨nman ki apa a. Si w ap lÃ¨ l sÃ¨vi avÃ¨k sonde, oswa si ou pa ap lÃ¨ l sÃ¨vi avÃ¨k AnchÃ¨nman nan tout nan tablo regle ou, sipresyon se aktyÃ¨lman reyÃ¨lman fasil. Tout sa ou bezwen fÃ¨ se Hash nan done, ak LÃ¨ sa a ale nan ki kote. Apre sa, an konsideran ou pa fÃ¨ sa gen nenpÃ²t kolizyon, ou pral kapab yo efase trÃ¨ vit. 

Koulye a, Passage a se kote bagay sa yo jwenn yon ti kras pi plis konplike. Li nan an mwayÃ¨n pi bon pase lis lye. Si w ap lÃ¨ l sÃ¨vi avÃ¨k AnchÃ¨nman, ou toujou gen yon lis lye, ki vle di ou toujou gen nan rechÃ¨ch detriman yon lis lye. Men, paske se w ap pran lye ou lis ak divize li sou 100 oswa 1,000 oswa n eleman nan tablo regle ou, w ap lis lye, yo tout yon sÃ¨l nyÃ¨m gwosÃ¨ a. Yo ap tout anpil pi piti. Ou te n lye lis olye pou nan yon sÃ¨l lis lye nan gwosÃ¨ n. 

Se konsa, sa a-mond reyÃ¨l konstan faktÃ¨, nou jeneralman pa pale sou nan tan konpleksite, li aktyÃ¨lman fÃ¨ yon diferans isit la. Se konsa, Passage se toujou lineyÃ¨ rechÃ¨ch si w ap itilize AnchÃ¨nman, men longÃ¨ a nan lis la w ap chÃ¨che a se trÃ¨, trÃ¨ kout pa konparezon. Yon fwa ankÃ², si se ou klasman Objektif isit la, regle tab la pwobableman pa chemen ki dwat la yo ale. Jis itilize yon etalaj si klasman se reyÃ¨lman enpÃ²tan ba ou. 

Apre sa, yo ka kouri gam la nan gwosÃ¨. Li difisil yo di si yon tab regle se ti piti oubyen gwo, paske li reyÃ¨lman depann de ki jan gwo tab regle ou a se. Si w ap sÃ¨lman ale nan dwe estoke senk eleman nan tablo regle ou, epi ou gen yon tab regle ak 10,000 eleman nan li, w ap pwobableman gaspiye yon anpil nan espas. KontrÃ¨man ke yo te ou ka tou gen tab regle trÃ¨ kontra enfÃ²mÃ¨l ant, men ki pi piti tab la regle ou vin, ankÃ² nan chak nan sa yo bay lis lye vin. Se konsa, gen nan reyÃ¨lman pa gen fason yo defini egzakteman gwosÃ¨ a nan yon tab regle, men li la pwobableman ki an sekirite yo di li nan jeneralman pral fÃ¨ pi gwo pase yon lye lis estoke done a menm, men ki pi piti pase yon trye. 

Epi eseye yo katriyÃ¨m lan nan sa yo estrikti ke nou ve yo te ap pale de. Mete nan yon trye se konplÃ¨ks. Genyen yon anpil nan dinamik alokasyon memwa, espesyalman nan kÃ²mansman an, jan ou ap kÃ²manse yo bati. Men, li lÃ¨ konstan. Li nan sÃ¨lman eleman imen an isit la ki fÃ¨ li difisil. Ãske w gen yo rankontre null konsÃ¨y, malok espas, ale la, espas pÃ¨tÃ¨t malok apati de la ankÃ². SÃ²t la nan faktÃ¨ a entimidasyon endikasyon nan alokasyon memwa dinamik se obstak nan klÃ¨. Men, yon fwa ou te otorize li, ensÃ¨syon aktyÃ¨lman vini byen senp, epi li sÃ¨tÃ¨nman se tan konstan. 

Sipresyon se fasil. Tout sa ou bezwen fÃ¨ se navige desann yon koup la endikasyon ak gratis ne la, se konsa sa a, se trÃ¨ bon. Passage se tou trÃ¨ vit. Li nan sÃ¨lman ki baze sou la longÃ¨ done ou. Se konsa, si tout done ou a se senk strings karaktÃ¨, pou egzanp, w ap estoke senk strings karaktÃ¨ nan trye ou, li sÃ¨lman pran senk etap sa yo jwenn sa ou ap chÃ¨che pou. Senk se jis yon faktÃ¨ konstan, se konsa ankÃ², ensÃ¨syon, sipresyon, ak Passage isit la yo se tout tan tout tan konstan, efektivman. 

Yon lÃ²t bagay se ke trye ou a se aktyÃ¨lman kalite deja klase, dwa? Pa vÃ¨ti nan ki jan nou ap mete eleman, pa ale lÃ¨t pa lÃ¨t nan an kle, oswa chif pa chif a kle a, tipikman, trye ou fini moute ke yo te kalite Ranje jan ou bati l '. Li pa vrÃ¨man fÃ¨ sans nan panse osijÃ¨ de Fouye nan menm fason an nou panse osijÃ¨ de l 'ak ranje, oswa lis lye, oswa regle tab. Men, nan kÃ¨k sans, ou trye se Klase jan ou ale. 

InconvÃ©nient la, nan kou, se ke yon trye rapidman vin gwo. Soti nan chak pwen junction, ou ta ka en-si kle ou konsiste de chif, ou gen 10 lÃ²t kote ou ka ale, ki vle di ke chak ne gen enfÃ²masyon sou done yo ou vle nan magazen nan ki ne, plis 10 endikasyon. Ki, sou CS50 IDE, se 80 bytes. Se konsa, li omwen 80 bytes pou chak ne ke ou kreye, ak ki pa nan menm konte done. Men, si ou yo nÅuds lÃ¨t olye pou yo chif, kounye a ou gen 26 endikasyon soti nan tout kote. Ak 26 fwa 8 se pwobableman 200 bytes, oswa yon bagay tankou sa. Epi ou gen kapital ak miniskil ou ka wÃ¨ ki kote mwen pral ak sa a, dwa? NÅuds ou ka jwenn vrÃ¨man gwo, e konsa trye nan tÃ¨t li, an jeneral, kapab jwenn vrÃ¨man gwo, tou. Se konsa, si espas se nan yon wo prim sou sistÃ¨m ou a, yon trye pa ta ka wout la dwa ale, menm si lÃ²t benefis li yo antre nan jwe. Mwen se Doug Lloyd. Sa a se CS50.