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.