[MUSIC JOC]
>> DAVID MALAN: Aceasta este CS50.
Și acest lucru este atât de început și end-- ca literally-- aproape de sfârșitul
de sase saptamani.
>> M-am gândit împărtășesc o pic de un fapt distracție.
Am scos asta de la un Date semestru dribleze cuprinse.
Vă amintiți că vă cerem pe fiecare Formularul set p, dacă ați vizionat on-line
sau dacă ați participat în persoană.
Și aici este de date.
Așa că astăzi a fost foarte mult previzibil.
Dar ne-am dorit să-și petreacă un pic de timp cu tine, totuși.
Vrea cineva să presupunem ce acest grafic este atât de jaggy, sus în jos, în sus în jos,
astfel în mod constant?
Ce face fiecare dintre vârfurilor și jgheaburi reprezinta?
>> Audiența: [inaudibil]
DAVID MALAN: Într-adevăr.
Și mai amuzant, Doamne ferește, avem o prelegere pe o zi de vineri
la începutul semestrului, asta e ceea ce vedem întâmpla.
Așa că astăzi, ne împărtășim într-un pic mai multe despre structuri de date.
Și pentru a vă oferi mai mult de un solid model mental pentru probleme la cinci,
care este acum afară.
Greșeli de ortografie, care, vom tu dai un fișier text oarecare 100.000
plus cuvinte în limba engleză, și ai de gând să aibă
să dau seama cum să le încărcați inteligent în memorie, în memoria RAM, folosind unele date
structura de alegerea ta.
>> Acum, o astfel de structură de date ar putea fi, dar probabil nu ar trebui să fie,
lista destul de simplist legate, pe care am introdus ultima dată.
Și o listă legat avut cel puțin un avantaj pe o matrice.
Ce este un avantaj al o listă legată, fără îndoială?
>> Audiența: de inserție.
>> DAVID MALAN: de inserție.
Ce vrei să spui cu asta?
>> Audiența: Oriunde de-a lungul lista [neauzit].
>> DAVID MALAN: Bun.
Astfel încât să puteți introduce un element de oriunde vrei în mijlocul listei
fără a fi nevoie să shuffle nimic, care am ajuns la concluzia, în opțiunea de sortare nostru
discuții, nu este neapărat un lucru bun,
pentru că este nevoie de timp pentru a trece de fapt toate aceste oameni la stânga sau la dreapta.
Și așa cu o listă legată, puteți doar aloca cu malloc, un nou nod,
și apoi să actualizeze un cuplu de pointers-- două, trei operațiuni max--
și suntem capabili să Fanta de cineva în orice destinație într-o listă.
>> Ce altceva era avantajos despre o listă legat?
Da?
>> Audiența: [inaudibil]
DAVID MALAN: Perfect.
Perfect.
E foarte dinamic.
Și că nu ești comiterea, în prealabil, într-o anumită dimensiune fixă
bucată de memorie, ca tine ar trebui a, cu o serie, în sensul creșterii de care
este că puteți aloca noduri numai pe Cererea astfel folosind doar cât mai mult spațiu
cum ai de fapt nevoie.
Prin contrast cu o serie, s-ar putea aloca accidental prea puțin.
Și apoi e doar de gând a fi o durere în gât
să realoce o nouă gamă mai mare, copiați totul peste, desprindă matrice vechi,
și apoi mutați despre afacerea ta.
Sau, mai rău, s-ar putea aloca fel mai multă memorie decât în ​​realitate nevoie,
și astfel vei avea o foarte matrice slab populate, ca să spunem așa.
>> Deci, o listă legată vă oferă aceste Avantajele de dinamism și flexibilitate
cu inserții și deleții.
Dar cu siguranță trebuie să existe un preț plătit.
De fapt, una dintre temele explorat pe test de zero
a fost o pereche de compromisurile am văzut până acum.
Deci, ce este un preț plătit sau de o Dezavantajul unei liste legat?
Da.
>> Audiența: Nu există acces aleator.
>> DAVID MALAN: Nu există acces aleator.
Dar cui îi pasă?
Cu acces aleator nu sună convingător.
>> Audiența: [inaudibil]
DAVID MALAN: Exact.
Dacă doriți să aveți un anumit algorithm--
și lasă-mă să propună de fapt binar de căutare în special, care
este una am folosit destul de bit-- dacă nu aveți acces aleator,
nu poți face asta aritmetică simplă de a găsi, cum ar fi elementul de mijloc
și sari dreptul la ea.
Ai în schimb să înceapă de la prima Element si cauta liniar de la stânga
la dreapta, dacă doriți să găsiți mijloc sau orice alt element.
>> Audiența: Probabil este nevoie de mai multă memorie.
>> DAVID MALAN: ia mai mult de memorie.
Unde este acea suplimentar costa provenind din memorie?
>> Audiența: [inaudibil]
DAVID MALAN: Exact.
În acest caz aici, am avut o listă legată de numere întregi,
și totuși suntem dublare cantitatea de memorie
avem nevoie de asemenea stocarea aceste indicii.
Acum mai puțin de o afacere de mare ca structs dvs. să obțineți mai mare
si tu esti stocarea nu un număr, dar poate un student sau un alt obiect.
Dar punctul rămâne cu siguranță.
Și astfel un număr de operațiunile pe liste legate au fost chemați
au fost O mare de liniar N-.
Lucruri, cum ar fi de introducere sau de căutare sau ștergere în cazul în care un element
sa întâmplat să fie la sfârșitul lui lista dacă este sortate sau nu.
>> Uneori s-ar putea avea noroc și în limite așa mai mici pe aceste operațiuni
ar putea fi, de asemenea, timp constant daca esti mereu în căutarea la primul element,
de exemplu.
Dar în cele din urmă, ne-am promis pentru a realiza Sfântul Graal
de structuri de date, sau unele acestora aproximare,
cu titlu de timp constant.
Poate găsim elemente sau adăuga elemente sau elimina elemente dintr-o listă?
Vom vedea destul de repede.
Și se pare că o mecanismelor suntem
O să înceapă să folosească astăzi, consumului anual în p stabilit cinci,
este, de fapt destul de familiar.
De exemplu, în cazul în care acest lucru este un buchet de cărți de examen, fiecare dintre care
are un student în primul rând si nume pe ea,
și le-am ridica de la la sfârșitul unui examen,
și toate acestea sunt destul de mai mult într-o ordine aleatorie,
și vrem să mergem cu privire la sortarea aceste examene, astfel că, odată clasificate
e doar o mult mai ușor și mai repede pentru a le înmâna înapoi
pentru studenții alfabet.
Care ar fi instinctele tale pentru o gramada de examene, cum ar fi aceasta?
>> Ei bine, daca esti ca mine, s-ar putea vedea că aceasta este m,
așa că am de gând să fel de a pune acest lucru în, în cazul în care acest lucru este masa mea sau în cazul în care podeaua mea
Sunt de raspandire lucruri out-- sau matrice mea really--
S-ar putea pune toate ms acolo.
Oh.
Iată un A. Deci, eu s-ar putea a pus As aici.
Oh.
Iată un alt A. am de gând pentru a pune asta pe aici.
Iată un Z. Aici este un alt M. Și așa S-ar putea începe a face grămezi de acest gen.
Și atunci poate că m-aș duce în mai târziu și un fel de foarte nitpicky-ly fel
grămezi individuale.
Dar ideea este m-aș uita la intrare că sunt jucători
și aș face ceva calculate decizie bazată pe acea intrare.
În cazul în care începe cu A, el a pus acolo.
În cazul în care începe cu Z, pune-l peste acolo, și totul în între.
>> Deci, aceasta este o tehnica care este în general, cunoscut sub numele hashing-- H-A-S--H
ceea ce, în general, înseamnă a lua ca de intrare și folosirea acea intrare pentru a calcula
o valoare, în general, un număr, și că Numărul este indicele într-o depozitare
container, ca un tablou.
Deci, cu alte cuvinte, am putea avea un funcție hash, așa cum fac eu în capul meu,
că dacă văd pe cineva e Numele care începe cu A,
Am de gând să hartă care la zero în capul meu.
Și dacă am vedea pe cineva cu Z, eu sunt O să hartă care la 25 în capul meu
și apoi a pus că în ultima cel mai gramada.
>> Acum, dacă te gândești nu creierul meu dar un program C, ceea ce ar putea numere
te bazezi pe pentru a obține același rezultat?
Cu alte cuvinte, dacă a avut ASCII de caractere A,
Cum se determina ceea ce găleată să-l pună în?
Probabil că nu vreau să pune-l în găleată 65 de ani, care
Ar fi ca și cum acolo pentru nici un motiv bun.
În cazul în care vrei să pună A în ceea ce privește valoarea ASCII?
În cazul în care vrei să faci pentru a ASCII sale Valoarea de a veni cu o găleată inteligentă
a pus-o în?
>> Audiența: Minus A.
>> DAVID MALAN: Da.
Deci, minus A sau minus în mod specific 65 dacă e
o A. de capital sau 98, dacă este o literă mică o.
Și așa încât ne-ar permite să, foarte pur și simplu și foarte aritmetic,
pune ceva într-o găleată de genul asta.
Deci, se dovedește facem de fapt aceasta, de asemenea, chiar cu chestionare.
>> Deci, s-ar putea aminti tu încercuite ta Numele colegi învățătura lui pe coperta.
Și au fost organizate numele TF în aceste coloane alfabetic
bine, crezi sau nu, atunci când toate 80 plus noi
s-au reunit noaptea de calitate, ultima etapă în procesul de clasificare
este de a hash chestionare într-o mare spațiu de podea la [inaudibil]
și să se stabilească teste tuturor afară în exact ordinea de lor TF
Numele de pe capacul, deoarece atunci este mult mai ușor pentru noi
pentru a căuta prin faptul că utilizarea liniar caută sau un fel de inteligență
pentru un TF pentru a găsi sau a lui chestionare elevilor ei.
>> Deci, această idee de hash pe care le veți vedea este
destul de puternic este, de fapt destul de obișnuit și foarte intuitiv,
mai mult ca probabil, diviza și cucerire a fost în săptămâna zero.
Am nerăbdare rapid la hackathon un cuplu de ani în urmă.
Aceasta a fost Zamyla și un cuplu de alți studenți salut personal
așa cum au venit în.
Și am avut o grămadă de pliere Mese de acolo cu etichete de nume.
Și ne-am etichetele de nume organizat cu la fel ca și peste acolo
și Zs acolo.
Și astfel unul dintre cele TFS foarte inteligent a scris acest lucru ca instrucțiunile
pentru a doua zi.
Și în săptămâna 12 a semestrului aceasta a făcut toate sens perfect și toată lumea
știa ce să facă.
Dar oricând ai coada de așteptare în același mod,
te punerea în aplicare a aceeași noțiune de un hash.
Deci, haideți să-l un pic oficializa.
Aici este un tablou.
Este atras de a fi un pic largă doar pentru a descrie, vizual,
pe care le-ar putea pune siruri de caractere în așa ceva.
Și aceasta matrice este în mod clar din numărul total de dimensiune 26.
Și lucrul se numește tabel arbitrar.
Dar aceasta este doar de extrădare unui artist a ceea ce ar putea fi un tabel hash.
>> Deci, un tabel hash acum este de gând să să fie o structură de date de nivel superior.
La sfârșitul zilei suntem pe cale de a vedea pe care le
poate pune în aplicare un tabel hash, care este de mult ca linia de check-in
la un Hackathon mult ca aceasta Tabelul folosit pentru sortarea cărți de examen.
Dar un tabel hash este un fel de acest nivel înalt
concept care ar putea folosi o matrice sub capota să-l pună în aplicare,
sau ar putea folosi o listă de lungime, sau chiar probabil, alte structuri de date.
Și acum asta e prelevarea theme-- unele dintre aceste ingrediente fundamentale
ca o matrice și această clădire bloc acum de o listă de lungime
și de a vedea ce altceva putem construi pe partea de sus a acestora, cum ar fi ingredientele
într-o rețetă, ce mai mult Rezultatele finale interesante și utile.
>> Deci, cu tabelul hash putem să o pună în aplicare
în memorie pictural ca aceasta, dar cum s-ar putea să fie de fapt codificate în sus?
Ei bine, poate ca pur si simplu este aceasta.
În cazul în care CAPACITATE în toate capace, este doar unele constant-- de exemplu 26,
pentru 26 de litere ale alphabet-- Am putea numi masa mea variabil,
și-ar putea pretinde că am de gând să a pus stele char acolo, sau string.
Deci, este la fel de simplu ca acest lucru dacă doresc să pună în aplicare un tabel hash.
Și totuși, aceasta este de fapt doar un tablou.
Dar, din nou, un hash tabel este acum ce vom
apela un tip de date abstract asta e doar un fel de stratificare conceptual pe partea de sus
de ceva mai lumesc ca acum o matrice.
>> Acum, cum putem merge despre rezolvarea problemelor?
Ei bine, mai devreme am avut luxul de a avea spațiu de tabelă suficient aici
astfel încât am putut pune teste oriunde am vrut.
Deci, ceea ce ar putea merge aici.
Zs ar putea merge aici.
Dna ar putea merge aici.
Și apoi am avut ceva spațiu suplimentar.
Dar aceasta este un pic de un drept ieftin acum, deoarece acest tabel, dacă am într-adevăr
gândit la ea ca la o matrice, este doar Va fi de o anumită dimensiune fixă.
>> Deci, punct de vedere tehnic, dacă am trage până quiz un alt elev
și a se vedea, oh, această persoană Numele începe cu un A de asemenea,
Am facut un fel de doresc să-l pună acolo.
Dar, de îndată ce am pus-o acolo, în cazul în care acest tabel reprezintă într-adevăr o matrice,
Am de gând să fie imperative sau clobbering oricine test acest student este.
Dreapta?
Dacă aceasta este o matrice, un singur lucru poate du-te în fiecare dintre aceste celule sau elemente.
Și așa am cam avea de a alege și de a alege.
>> Acum, mai devreme am facut un fel de înșelat și a făcut acest lucru sau I
doar un fel de stivuite ele deasupra celeilalte.
Dar asta nu se va zbura în cod.
Deci, în cazul în care aș putea să îl al doilea elev al cărui nume
este o dacă tot ce am avut asta spațiu tabelă disponibil?
Și l-am folosit trei sloturi și ea Se pare ca exista doar cateva alții.
Ce ai putea face?
Audiența: [inaudibil]
DAVID MALAN: Da.
Poate că hai să-l păstrați simplu.
Dreapta?
Ea nu se potrivește în cazul în care vreau să-l puneți.
Așa că am de gând să-l puneți punct de vedere tehnic în cazul în care B ar merge.
Acum, desigur, încep să mă picta într-un colț.
Dacă aș ajunge la un elev al cărui nume este, de fapt B,
acum B va fi mutat un pic înainte, așa cum s-ar putea întâmpla, da,
în cazul în care acest lucru este un B, acum trebuie să meargă aici.
>> Și astfel acest lucru foarte repede ar putea deveni problematic,
dar este o tehnica care de fapt este menționată ca liniar palpare,
prin care doar considerați dumneavoastră matrice a fi de-a lungul liniei.
Și tu doar un fel de sonda sau inspecta fiecare element disponibile
Cautati un loc disponibil.
Și, de îndată ce veți găsi unul, îl picătură acolo.
>> Acum, prețul fiind plătit acum pentru această soluție este ceea ce?
Avem o gamă dimensiune fixă, și atunci când am insera nume
în ea, cel puțin la început, ceea ce este timpul de execuție de inserție
pentru a pune elevilor teste în gălețile potrivite?
Big O de ce?
>> Audiența: n.
DAVID MALAN: Am auzit O mare de n.
Nu este adevărat.
Dar vom tachineze pe langa de ce într-o clipă.
Ce altceva ar putea fi?
>> Audiența: [inaudibil]
DAVID MALAN: Și lasă-mă să o fac vizual.
Deci, să presupunem că aceasta este litera S.
>> Audiența: E una.
DAVID MALAN: E una.
Dreapta?
Aceasta este o matrice, care înseamnă că avem acces aleator.
Și dacă ne gândim la acest lucru ca zero și acest lucru ca 25,
și ne dăm seama că, oh, aici e intrarea mea S,
Eu pot converti cu siguranță S, un caracter ASCII,
la un număr corespunzător între zero și 25
și apoi imediat pune-l în cazul în care acesta face parte.
>> Dar, desigur, de îndată ce ajung la a doua persoană care e numele este A sau B sau C
în cele din urmă, dacă l-am folosit liniar palpare ca soluția mea,
timpul de execuție a inserarea în cel mai rău caz
este, de fapt de gând să revină în ce?
Și l-am auzit aici corect de timpuriu.
Audiența: [inaudibil]
DAVID MALAN: Deci, este într-adevăr n dată Ai un set suficient de mare de date.
Deci, pe de o parte, dacă matrice este destul de mare
și datele dumneavoastră este destul de rare, tu primi acest moment frumos constant.
Dar, de îndată ce începe să obtinerea mai multe și mai multe elemente,
și doar statistic te mai multe persoane cu litera
A ca numele lor sau litera B, ea ar putea potențial
involua într ceva mai liniar.
Deci, nu destul de perfect.
Deci, am putea face mai bine?
>> Ei bine, ce a fost nostru soluție înainte de când ne-am
doresc să aibă mai mult dinamism mult permis ceva de genul un tablou?
Audiența: [inaudibil]
DAVID MALAN: Ce am introduce?
Da.
Deci, o listă legat.
Ei bine, să vedem ce legătură o Lista ar putea face pentru noi în schimb.
Ei bine, lasă-mă să propună noi trage imaginea, după cum urmează.
Acum, aceasta este un alt imagine de la un exemplu
dintr-un text diferit, de fapt, că este, de fapt, folosind o serie de dimensiuni 31.
Și acest autor pur și simplu a decis să hash siruri de caractere
nu se bazează pe numele persoanei, dar bazat pe zile de naștere lor.
Indiferent de luni, au gândit dacă te-ai născut pe primul dintr-o lună
sau 31 a lunii, autorul va hash bazat pe acea valoare,
astfel încât să se răspândească numele un pic mai mult decât 26 de locuri s-ar putea permite.
Și poate că e un pic mai uniformă decât a merge cu litere alfabetice,
pentru că, desigur, nu e probabil mai multe persoane în lume, cu nume
care începe cu A mare de siguranță alte litere ale alfabetului.
Deci, poate că acest lucru este un pic mai uniform, presupunând
o distribuție uniformă de copii într-o lună.
>> Dar, desigur, acest lucru este încă imperfect.
Dreapta?
Avem coliziuni.
Mai multe persoane din acest Structura de date sunt încă
având aceeași data nașterii, cel puțin esti indiferent de lună.
Dar ceea ce a făcut autorul?
Ei bine, se pare ca avem un tablou pe partea stângă trase vertical,
dar asta e doar extrădare unui artist.
Nu contează ce direcție te desena o matrice, este încă o matrice.
Ce este aceasta o serie de aparent?
>> Audiența: Lista de legat.
>> DAVID MALAN: Da.
Se pare că e un serie de liste legate.
Deci, din nou, la acest punct de gen de utilizare a acestor structuri de date acum
ca ingrediente pentru mai multe soluții interesante,
puteți lua absolut o fundamental, ca o matrice,
și apoi să ia ceva mai mult interesant ca o listă legată
și chiar să le combine într-o mai structură de date mai interesant.
Și într-adevăr, acest lucru prea ar fi fi numit un tabel hash,
prin matrice este într-adevăr tabel hash,
dar că tabelă de dispersie a lanțuri, ca să spunem așa,
care poate crește sau micșora în funcție, pe de Numărul de elemente pe care doriți să inserați.
>> Acum, în consecință, ceea ce este Timpul de funcționare acum?
Dacă vreau să inserați cineva a cărui zi de naștere este 31 octombrie,
unde are el sau ea merge?
Bine.
În partea de jos, unde se spune 31.
Și asta e perfect.
Asta a fost timp constant.
Dar ce se întâmplă dacă vom găsi pe altcineva a cărui zi de naștere este, să vedem,
Octombrie, noiembrie, 31 Decembrie?
În cazul în care el sau ea este de gând să meargă?
Același lucru.
În două etape, totuși.
Asta e constant, deși nu-i așa?
Bine.
În momentul de față este.
Dar, în cazul general, mai multe persoane pe care le adăugăm,
probabilistic, mergem pentru a obține mai multe și mai multe coliziuni.
>> Acum, acest lucru este un pic mai bine pentru că tehnic
acum lanțurile mele ar putea fi în cel mai rău caz cât timp?
Dacă aș insera n oameni în acest mai mult structură de date sofisticat, n oameni,
în cel mai rău caz o să fie n.
De ce?
>> Audiența: Pentru că dacă toată lumea are aceeași zi de naștere,
ei vor fi o singură linie.
DAVID MALAN: Perfect.
Ar putea fi un pic contrived, dar cu adevărat în cel mai rău caz,
dacă toată lumea are aceeași zi de naștere, ținând cont de inputuri care le ai,
ai de gând să aibă o lanț masiv lung.
Și așa, ai putea apela un hash masă, dar de fapt e
doar o listă masiv în legătură cu o mulțime de spațiu irosit.
Dar, în general, dacă presupunem că cel puțin aniversari sunt uniform--
și, probabil, nu este.
Fac asta.
Dar dacă presupunem, pentru dragul discuției
că ele sunt, apoi, în teorie, dacă aceasta este reprezentarea verticală
de matrice, și atunci sperăm că ești mergi la a lua lanțuri, care sunt, știți,
aproximativ aceeași lungime în care fiecare dintre acestea reprezintă o zi a lunii.
>> Acum, dacă e 31 zile din luna, ceea ce înseamnă că timpul meu de rulare într-adevăr
este O mare de n peste 31, care se simte mai bine decât liniar.
Dar ceea ce a fost unul dintre noastre angajamente câteva săptămâni
acum ori de câte ori a venit la exprimarea timpul de execuție a unui algoritm?
Uită-te numai la termenul ridicat comanda.
Dreapta?
31 este cu siguranta de ajutor.
Dar aceasta este încă O mare de n.
Dar una dintre temele problemei stabilit cinci
va fi de recunosc că absolut,
asimptotic, teoretic această structură de date
nu este mai bună decât o listă legată masiv.
Și într-adevăr, în cel mai rău caz, acest tabelă de dispersie s-ar putea să revină în asta.
>> Dar în lumea reală, cu noi oamenii că Mac-urile sau PC-uri proprii sau orice
și se execută din lumea reală software-ul pe date din lumea reală,
care algoritm ai de gând să preferi?
Cel care ia măsuri finali sau una care ia n împărțit la 31 de pași
pentru a găsi unele bucată de date sau pentru a căuta unele informații?
Adică, absolut cele 31 de mărci o diferență în lumea reală.
Acesta este de 31 ori mai rapid.
Și noi, oamenii sunt cu siguranță O să apreciez asta.
>> Deci, dau seama de dihotomia acolo între realitate
vorbind despre lucruri teoretic și asimptotic care cu siguranta
are valoare cum am văzut, dar în lumea reală,
dacă îți pasă doar punerea fericit om de intrări generale,
ați putea dori foarte bine să accepte faptul că, da, aceasta este liniar,
dar e de 31 de ori mai rapid decât liniar ar putea fi.
Și mai bine, noi nu trebuie doar să face ceva arbitrar ca o zi de naștere,
am putea petrece un pic mai mult timp și inteligență
și cred despre ceea ce am putea face, dat numele unei persoane și, poate,
Data nașterii lor de a combina cele ingrediente pentru a descoperi ceva
care este cu adevărat mai mult uniform și mai puțin jaggy,
ca să spunem așa decât această imagine în prezent sugerează că ar putea fi.
Cum am putea pune în aplicare acest lucru în cod?
Ei bine, lasă-mă să propună noi doar împrumuta unele sintaxă ne-am
folosit de câteva ori până acum.
Și am de gând să definească un nod, care din nou
este un termen generic pentru doar câteva container pentru unele structuri de date.
Am de gând să propună un șir se întâmplă acolo.
Dar vom începe să luați cele de formare roți de pe acum.
>> Nu mai bibliotecă CS50 într-adevăr, cu excepția cazului în care doriți
să-l utilizați pentru finală dvs. proiect, ceea ce este bine,
dar acum vom trage înapoi cortina și spun că este doar o stea char.
Deci, cuvântul acolo va fi numele persoanei în cauză.
Și acum am un link aici la nodul următor
astfel încât acestea să reprezinte fiecare dintre nodurile
în lanț, potențial, de o listă legată.
>> Și acum cum fac eu declar tabelul hash în sine?
Cum pot declara tot această structură?
Ei bine, într-adevăr, la fel ca am folosit un pointer la doar primul element al unei liste
înainte, în mod similar, pot să spun doar Am nevoie doar de o grămadă de indicii
să pună în aplicare acest tabel hash întreg.
Am de gând să aibă o matrice numita masă pentru tabelă de dispersie.
O să aibă o capacitate dimensiune.
Asta-i cât de multe elemente pot încăpea în el.
Și fiecare dintre aceste elemente în acest matrice va fi o stea nod.
De ce?
Ei bine, pe această imagine, ceea ce am de punere în aplicare a tabelului hash ca
în mod eficient la început este doar această matrice pe care le-am desenat pe verticală,
fiecare dintre căror pătrate reprezintă un pointer.
Ca cei care au slash-uri prin ele sunt doar nule.
Și cei care au săgeți care merg la dreapta
sunt indicii reale cu noduri reale, ergo la începutul unei liste legate.
>> Deci, aici, atunci, este modul în care s-ar putea să pună în aplicare un tabel hash care
pune în aplicare înlănțuire separat.
Acum putem face mai bine?
Bine am promis ultima dată că am putea realiza timp constant.
Și eu un fel de ți-a dat constanta de timp aici,
dar atunci nu a spus într-adevăr constantă de timp, deoarece este încă
dependentă total număr de elemente
te introducere în structura de date.
Dar să presupunem că am făcut asta.
Lasă-mă să mă întorc la ecranul pe aici.
Permiteți-mi să proiecteze asta aici, clar ecran, și să presupunem că am făcut asta.
Să presupunem că am vrut pentru a introduce numele Daven în în structura mea de date.
>> Așa că vreau să introduceți un șir Daven în structura de date.
Ce se întâmplă dacă nu folosesc un hash masă, dar am folosi
ceva care este mai mult copac-ca ca un arbore genealogic, în cazul în care
aveți unele rădăcină de la noduri și frunze de top și apoi
care merge în jos și spre exterior.
Să presupunem deci, că am vrea să introducă lui Daven
în ceea ce-i în prezent o listă goală.
Am de gând să fac următoarele: Sunt va crea un nod în această familie
copac ca structura de date care arată un pic de acest fel, fiecare dintre acestea
dreptunghiuri a, să zicem, de acum 26 elemente în ea.
Și fiecare dintre celulele în această matrice se întâmplă
pentru a reprezenta scrisoarea unui alfabet.
>> Mai exact, am de gând să trateze aceasta este A, apoi B, apoi C, apoi D,
asta de aici.
Deci, acest lucru se întâmplă pentru eficient reprezintă litera D.
Dar pentru a introduce toate lui Daven nume am nevoie pentru a face un pic mai mult.
Deci, eu în primul rând de gând să hash, ca să spunem așa.
Am de gând să se uite la prima literă în a Daven care este, evident, un D,
și am de gând să aloce un nod care arată
ca asta: un dreptunghi mare mare suficient pentru a se potrivi tot alfabetul.
>> Acum, D se face.
Acum A. D-A-V-E-N este gol.
Deci, acum ce am de gând să fac asta.
De îndată ce am început Notă D nu exista nici pointer acolo.
Este valori de gunoi în acest moment, sau I s-ar putea inițializa la null.
Dar permiteți-mi să continui cu această idee de a construi un copac.
Lasă-mă să aloce un alt una dintre acestea noduri, care are 26 de elemente în ea.
>> Și știi ce?
În cazul în care acest lucru este doar un nod în memorie care Am creat cu malloc, folosind un struct
așa cum vom vedea în curând, Am de gând să fac asta:
Am de gând să tragă o săgeată de la lucru care a reprezentat D jos
la acest nou nod.
Și acum, în primul rând în următorii scrisoare în numele Daven lui,
V-- D-A-V-- am de gând să merg mai departe și să tragă un alt nod ca aceasta,
prin care, elementele V aici, care vom trage pentru Hopa instance--.
Nu vom trage acolo.
O să merg aici.
>> Apoi, vom consideră acest lucru ca fiind V.
Și apoi aici vom index jos de la V în ceea ce vom considera E.
Și apoi de aici vom du-te să aveți una dintre aceste noduri aici.
Și acum avem o întrebare pentru a răspunde.
Trebuie să indice faptul că într-un fel suntem la sfârșitul șirului Daven.
Așa că am putut pleca doar nul.
>> Dar ce se întâmplă dacă avem de Daven numele complet, de asemenea, care
este, așa cum ne-am spus, Davenport?
Și ce dacă Daven este de fapt un subșir,
un prefix de un șir mult mai lung?
Noi nu putem doar permanent nu spun nimic se întâmplă
pentru a merge acolo, pentru că am putut nu introduceți niciodată un cuvânt ca Davenport
în această structură de date
>> Deci, ce am putea face în schimb este trata fiecare dintre aceste elemente
cum poate avea două elemente din interiorul ei.
Una dintre ele este un pointer, într-adevăr, așa cum am făcut.
Deci, fiecare dintre aceste cutii nu este doar o celulă.
Dar dacă în partea de sus Unu cea de jos a
va fi nul, pentru că nu există nici o Davenport doar încă.
Ce se întâmplă dacă cel de sus este o valoare specială?
Și că va fi un pic greu să-l această dimensiune trage.
Dar să presupunem că e doar o bifă.
Verifica.
D-A-V-E-N este un șir în această structură de date.
>> Între timp, dacă aș avea mai mult spațiu aici, aș putea face P-O-R-T,
și am putut pune check-in nodul care are litera T la sfârșitul.
Deci, acesta este un masiv -complex excelentă structură de date.
Și scrisul meu cu siguranță nu ajută.
Dar dacă am vrut să insera ceva altfel, ia în considerare ceea ce ne-ar face.
Dacă am vrut să pună pe David in, am urmeze aceeași logică, D-A-V,
dar acum aș vrea să subliniez în următorii Element nu de la E, dar de la I la D.
Deci nu va fi mai multe noduri în acest copac.
Vom avea malloc apel mai mult.
Dar eu nu vreau să fac o dezastru complet de această imagine.
Așa că haideți să în loc să se uite la un care a fost pre-formulate
ca acest lucru cu care nu dot, dot, puncte, dar tablouri doar prescurtate.
Dar fiecare dintre nodurile în acest copac de aici în sus
reprezintă același thing-- o serie Ray de dimensiune 26.
>> Sau, dacă vrem să fim într-adevăr corectă acum, ceea ce
dacă numele cuiva ca un apostrof, să
presupune că fiecare nod are de fapt ca 27 de indici în ea, nu doar 26.
Deci, acest lucru acum va fi un de date structura numita un trie-- T-R-I-E.
Un trie, care se presupune istoric un nume inteligent pentru un copac
care este optimizat pentru regăsire, care, desigur,
se scrie cu un I-E deci e trie.
Dar asta este istoria trie.
>> Deci, un trie este asta arborescentă structură ca un arbore genealogic
care în cele din urmă se comportă ca asta.
Și aici este doar un alt exemplu de grămadă de nume altor oameni.
Dar întrebarea acum la îndemână este ceea ce avem
am câștigat prin introducerea, fără îndoială, o mai structură de date complicate, și unul,
sincer, că folosește o mulțime de memorie.
>> Deoarece, chiar dacă, în acest moment, eu sunt doar
folosind D pointer și A și V și Es și NS,
Mă pierd un heck de mult de memorie.
Dar unde îmi petrec o resursă, Am tendința de a-mi câștiga înapoi altul.
Deci, dacă am petrece mai mult spațiu, ceea ce este, probabil, speranța?
Că eu îmi petrec mai puțin ce?
Audiența: Mai puțin timp.
DAVID MALAN: Time.
Acum, de ce ar putea fi asta?
Ei bine, ceea ce este inserția timp, în termeni de mare O acum,
de un nume ca Daven sau Davenport sau David?
Ei bine, Daven a fost de cinci etape.
Davenport ar fi nouă etape, asa ca ar fi o gamă mai mulți pași.
David ar fi de cinci etape la fel de bine.
Deci, acestea sunt beton numere, dar sigur nu e
o limită superioară lungime de numele cuiva.
Și într-adevăr, în problema seturi de cinci caietul de sarcini,
am de gând să propună asta e ceva
asta e de caractere de 40-unele-impar.
>> Realist, nimeni nu are un nume infinit lung,
care înseamnă că lungimea unei numele sau lungimea unui șir am putea
au anumite starea de structură este, fără îndoială, de ce?
E constant.
Dreapta?
Ar putea fi o constantă mare ca 40-ceva, dar este constantă.
Și nu are nici o dependență de cât de multe alte nume se află în această structură de date.
Cu alte cuvinte, dacă am a vrut să insera acum
Colton sau Gabriel sau Rob sau Zamyla sau Alison sau Belinda sau orice alt nume
de la personalul în aceste date structura, este timpul de funcționare
de a introduce alte nume va fi deloc afectate
de cât de multe alte elemente sunt în structura de date deja?
Nu e.
Dreapta?
Pentru că suntem în mod eficient folosind acest tabel hash multi-strat.
Și timpul de execuție a oricare dintre aceste operațiuni
nu depinde de numărul de elemente care sunt în structura de date
sau care sunt în cele din urmă de gând a fi în structura de date,
dar de durata ce anume?
>> Șirul fiind inserat, care nu face
acest asimptotic constant O mare time-- de unul.
Și sincer, doar în lumea reală, acest
înseamnă introducerea numele Daven lui ia cum ar fi cinci etape, sau Davenport nouă
trepte, sau David cinci etape.
Asta este al naibii de ori mici de funcționare.
Și, într-adevăr, e un foarte lucru bun, mai ales atunci când
nu este dependentă de totalul Numărul de elemente în acolo.
Deci, cum am putea pune în aplicare această tip de structură în codul?
E un pic mai mult complex, dar încă e
doar o cerere de blocuri de bază.
Am de gând să redefinească ne nod după cum urmează:
bool numit word-- și acest ar putea fi numit nimic.
Dar bool reprezintă ceea ce am desenat ca un semn de selectare.
Da.
Acesta este sfârșitul unui șir în această structură de date.
>> Și, desigur, steaua nod se referă la copii.
Și, într-adevăr, la fel ca un arbore genealogic, tu
ar lua în considerare nodurile care sunt agățat off
din partea de jos a unora părinte element de a fi copii.
Și astfel copiii este de gând să fie o serie de 27, cel 27
doar fiind de apostrof.
Mergem pentru a sorta de caz special care.
Astfel încât să puteți avea sigur nume cu apostrofuri.
Poate chiar ar trebui cratimă du-te acolo, dar veți
a se vedea în p set 5 doar am grijă despre scrisori și apostrofuri.
>> Și atunci cum Reprezentati structura de date în sine?
How do you reprezintă rădăcina din acest trie, ca să spunem așa?
Ei bine, la fel ca și cu o listă legată, tu au nevoie de un pointer la primul element.
Cu un trie ai nevoie doar de un singur pointer la rădăcina acestei trie.
Și de acolo puteți distribuire -ți de drum în jos adânc și mai adânc
la fiecare alt nod din structură.
Deci, pur și simplu, cu această cutie noi reprezentăm că struct.
>> Acum Meanwhile-- Oh, întrebare.
>> Audiența: Care e cuvântul bool?
>> DAVID MALAN: cuvânt Bool este doar aceasta incarnare C
din ceea ce am descris în această casetă de aici, atunci când
Am început să împartă fiecare dintre elemente în două bucăți array lui.
Una este un pointer la nodul următor.
De altă parte trebuie să fie ceva de genul o casetă de selectare
să spun da, există o cuvânt Daven că se termină aici,
pentru că nu vrem, în acest moment, Dave.
>> Chiar dacă Dave va fi o cuvânt legitim, că nu este în trie
încă.
Și D nu este un cuvânt.
Și D-A nu este un cuvânt sau un nume.
Deci, bifa indică o singură dată tu
a lovit acest nod este cale precedent de caractere
de fapt, un șir care le-ați introdus.
Deci, asta e tot bool acolo se face pentru noi.
>> Orice alte întrebări cu privire la încercări?
Da.
>> Audiența: Ce este suprapunerea?
Ce se întâmplă dacă aveți un Dave și o Daven?
DAVID MALAN: Perfect.
Ce se întâmplă dacă aveți un Dave și o Daven?
Deci, dacă am introduce, spune un pseudonim, pentru David-- Dave-- D-A-V-E?
Aceasta este de fapt foarte simplu.
Așa că doar de gând să ia patru etape.
D-A-V-E. Și ce trebuie să face o dată am lovit că al patrulea nod?
Doar de gând să verifice.
Suntem deja bine să plec.
Efectuat.
Patru pași.
Constanta de timp asimptotic.
Și acum am arătat că atât Dave și Daven sunt șiruri în structura.
Deci, nu este o problemă.
Și observați modul în care prezența de Daven nu-l face
să ia orice mai mult timp sau mai puțin timp de Dave și vice-versa.
>> Deci, ce altceva putem să facem acum?
Am folosit această metaforă înainte tăvi reprezentând ceva.
Dar se pare că o teanc de tăvi este de fapt
demonstrativ de un alt datelor abstract type-- o structură de date de nivel superior
că, la sfârșitul zilei este doar cum ar fi un tablou sau o listă de legat
sau ceva mai mult lumesc.
Dar este o mult mai interesant Conceptul conceptual.
Un teanc, cum ar fi acestea tăvilor aici, în Mather,
sunt, în general, numite doar that-- o stivă.
>> Și în acest tip de structură de date aveți două operations--
aveți unul numit apăsare pentru adăugând ceva la stiva,
cum ar fi punerea altă tavă înapoi pe partea de sus a stivei.
Și apoi pop, care înseamnă ia cel mai de sus off tavă.
Dar ceea ce este esențial despre o stivă este că ea are această caracteristică curios.
Ca personalul sala de mese sunt rearanjarea tăvile pentru masa urmatoare,
ce va fi adevărat despre modul în care elevii
interacționa cu această structură de date?
Audiența: Au de gând să pop un off.
DAVID MALAN: Au de gând să pop un off, sperăm, în partea de sus.
În caz contrar, e doar un fel de stupid pentru a merge tot drumul la partea de jos.
Dreapta?
Structura de date nu permite într-adevăr să vă apuca tava de jos, cel puțin
ușurință.
Deci, există această curios proprietate la o stivă
că ultimul element din este Va fi un prim out.
Si oamenii de stiinta de calculator apel acest LIFO-- ultimul intrat, primul ieșit.
Și este de fapt are aplicatii interesante.
Nu e neaparat la fel de evident ca unii alții, dar poate, într-adevăr, să fie util,
și poate, într-adevăr, să fie pus în aplicare într-o pereche de moduri diferite.
>> Așa că, și de fapt, să mă să nu se scufunde în asta.
Hai să facem acest lucru în schimb.
Să ne uităm la unul care e aproape aceeași idee, dar e un pic mai echitabilă.
Dreapta?
Daca esti unul dintre acesti baieti ventilator sau fete care îi place într-adevăr produsele Apple
și te-ai trezit la 3:00 să se alinieze la un magazin
pentru a obține cele mai recente foarte iPhone, tu ar fi coada de așteptare până ca aceasta.
>> Acum, o coadă este foarte deliberat pe nume.
E o linie pentru că există unii echitate la ea.
Dreapta?
Ar fel de supt, dacă ai ajuns acolo în primul rând la Apple Store
dar esti eficient de jos tavă pentru că angajații Apple a atunci
pop ultima persoană care de fapt, a intrat în linie.
Deci, stive și cozi, chiar dacă funcțional sunt un fel de same--
e doar această colecție de resurse care este
de gând să crească și shrink-- acolo a acest aspect corectitudine a acesteia,
cel puțin în lumea reală, la, în cazul în care operațiunile de efort fizic
sunt fundamental diferite.
Un stack-- o coadă rather-- se spune că au
două operațiuni de coadă: n și de cozi d.
Sau le puteți apela orice număr de lucruri.
Dar tu vrei doar pentru a capta ideea că unul este adăugarea
și unul este în cele din urmă scăzând.
>> Acum sub capota, atât stiva și o coadă ar putea fi puse în aplicare cât?
Nu vom merge în codul de aceasta deoarece nivelul superior
Ideea este un fel de mai evidentă.
Adică, ce fac oamenii?
Dacă eu sunt prima persoana de la Apple Stoca și aceasta este ușa din față,
Știi, am de gând să stau aici.
Și următoarea persoanei O să stau aici.
Deci, ce structură de date se pretează la o coadă?
>> Audiența: O coadă.
DAVID MALAN: Ei bine, o listă de așteptare.
Sigur.
Ce altceva?
>> Audiența: O listă legat.
>> DAVID MALAN: A postat lista pe care ar putea să pună în aplicare.
Și o listă legat este frumos, pentru că atunci aceasta poate crește în mod arbitrar de mult, spre deosebire de
de a avea un numar fix de oameni în magazin.
Dar poate un număr fix de locuri este legitim.
Pentru că dacă au doar ca 20 iPhone în prima zi, poate
au nevoie de doar o serie de dimensiuni 20 pentru a reprezenta coadă, ceea ce
este doar să spun acum, odată ce vom începe să vorbim despre aceste probleme de nivel superior,
puteți să-l pună în aplicare în orice număr de moduri.
Și există, probabil, doar de gând să fie un compromis în spațiu și timp
sau pur și simplu în propria complexitate cod.
>> Ce zici de o stivă?
Ei bine, o stivă, am vazut prea ar putea fi doar aceste tăvi.
Și ați putea pune în aplicare această o matrice.
Dar, la un moment dat, dacă utilizați o matrice, ce se va întâmpla cu tăvile
sunteți încercarea de a pune în jos?
Bine.
Te duci doar la să poată să meargă atât de mare.
Și cred că în Mather sunt de fapt, încastrate în acea deschidere.
Așa că, într-adevăr, e aproape ca Mather se utilizează
o serie de dimensiune fixă, pentru că poți doar
se potrivesc atât de multe tăvi în care deschiderea în perete jos de genunchi oamenilor.
Și astfel, care ar putea fi a declarat a fi o matrice,
dar am putea pune în aplicare cu siguranță că mai mult, în general, cu o listă legat.
>> Ei bine, ce zici de o altă structură de date?
Lasă-mă trage în sus un alt vizual aici.
Ceva de genul cum despre asta aici?
De ce s-ar putea fi util pentru a nu avea ceva la fel de fantezie ca un trie, care
am văzut avut aceste noduri foarte largi, fiecare dintre aceștia fiind într-o matrice?
Dar ce se întâmplă dacă facem ceva mai mult pur și simplu, ca un arbore genealogic de școală veche,
fiecare din ale cărui noduri aici doar stochează un număr.
În loc de un nume sau un descendent doar stochează un număr de genul asta.
>> Ei bine, jargonul vom folosi în structuri de date este atat încercări
și copaci, în cazul în care un trie, din nou, este doar unul a cărui noduri sunt tablouri,
este încă ceea ce s-ar putea utilizeze, începând cu școala primară
atunci când a făcut-o familie frunze tree-- și rădăcină
de copac și copii ai mamă și frații acestora.
Și am putea pune în aplicare un copac, de exemplu, la fel de simplu ca aceasta.
Un copac, în cazul în care ca un nod, unul dintre aceste cercuri, care are un număr,
ea nu va avea un pointer, dar doi.
Și, de îndată ce vă adăugați un al doilea indicator, tu
poate acum de fapt, face un fel de date bidimensional
Structuri din memorie.
Mai mult ca un bi-dimensional matrice, puteți
au un fel de două-dimensional Lista postat, dar cele
că urmează un model în cazul în care nu exista nici cicluri.
Este cu adevărat un copac cu un mod bunic aici și apoi
unii părinți și copii și nepoți și strănepoți.
și așa mai departe.
>> Dar ceea ce este cu adevarat elegant despre asta, doar pentru a vă tachineze cu ceva cod,
rechemare recursivitate de la un timp înapoi, prin care
vă scrie o funcție care se numește.
Aceasta este o oportunitate de frumos să pună în aplicare ceva
ca recursivitate, pentru că ia în considerare acest lucru.
>> Acesta este un copac.
Și eu am fost un pic anal cu cât Am pus numerele întregi în stradă.
Atât de mult, astfel că are o deosebită name-- un arbore binar de căutare.
Acum am auzit de binar căutare, dar poate tu
de lucru înapoi de la numele asta lui?
Care este modelul de cum am introduc numerele întregi în acest copac?
Nu e arbitrar.
Nu e ceva model.
Da.
>> Audiența: cele mai mici de pe partea stângă.
>> DAVID MALAN: Da.
Cele mai mici sunt pe partea stângă.
Cele mai mari sunt pe dreapta.
Astfel încât o afirmație adevărată este o mamă este mai mare decât copilul său stâng,
dar mai mică de copil dreptul său.
Și care singur este chiar un definiție verbal recursiv
pentru că puteți aplica asta aceeași logică a fiecărui nod
și ea doar fundul out, un caz de bază, dacă
va fi, atunci când a lovit unul dintre frunzele, ca să spunem așa,
în cazul în care un concediu mai are nici copii.
>> Acum, cum ar putea să vă găsi numărul 44?
Te-ar începe de la rădăcină și să spună, hm.
55 nu este 44 Și eu vreau să merg drept sau nu vreau să merg la stânga?
Ei bine, evident, vrei să mergi stanga.
Și așa e la fel ca la telefon exemplu de carte în căutare binar
mai general.
Dar suntem o punere în aplicare acum un pic mai dinamic
decât o matrice-ar putea permite.
Și, de fapt, dacă vrei să te uiți la codul, la prima vedere sigur.
Se pare ca o grămadă de linii.
Dar e frumos simplu.
Dacă doriți să pună în aplicare o funcție numit de căutare al cărui scop în viață
de a va cauta o valoare ca n, un număr întreg,
si tu esti trecut într-un pointer-- una un pointer la nodul de rădăcini,
mai degrabă, de acel copac din care puteți accesa orice altceva,
observa cât de direct puteți pune în aplicare logica.
Dacă copac este nul, în mod evident, nu e acolo.
Să se întoarcă false.
Dreapta?
Dacă vă predați-l nimic, nu e nimic acolo.
>> Altfel, dacă n este mai mic de sageata copac N- acum săgeată n,
amintesc am introdus super- scurt de altă zi,
și asta înseamnă că doar de-referința pointer si uita-te la câmpul numit n.
Deci, aceasta înseamnă du-te acolo și uita-te la câmpul numit n.
Deci, dacă n, valoarea bază dat, este mai puțin decât valoarea din întreg copaci,
în cazul în care vrei să mergi?
La stânga.
>> Deci, observați recursivitatea.
Eu returning-- nu este adevărat.
Nu este fals.
Mă întorc, indiferent de răspunsul este de la un apel la mine, care trece
un n din nou, care este redundantă, dar ceea ce este puțin diferit acum?
Cum mă face problema mai mica?
Sunt trece în drept a doua argument, nu rădăcină de copac,
dar copilul din stânga, în acest caz.
Deci, eu sunt asociate de la copilul din stânga.
>> Între timp, dacă n este mai mare decât nodul Eu sunt în prezent în căutarea la,
Caut de pe partea dreaptă.
Altfel, dacă pomul nu este nulă, și dacă elementul nu este la stânga
și nu e de dreapta, ceea ce este minunat în cazul?
Am descoperit, de fapt, nodul de la întrebare, și așa ne întoarcem adevărat.
>> Deci, tocmai am zgâriat suprafața acum unele dintre aceste structuri de date.
În problemă a seta cinci veți excursiile acestea încă mai departe,
și veți fi dat design-ul alegere a modului de a merge cu privire la acest lucru.
Ce aș vrea să închei pe este doar un al doilea teaser de 30
de ceea ce așteaptă săptămâna viitoare și dincolo.
>> Așa cum am begin-- din fericire s-ar putea think-- tranziție noastră încet
din lumea C și mai mic Detalii de implementare nivel,
într-o lume în care putem lua pentru a acordat că altcineva are în cele din urmă
puse în aplicare aceste date structuri pentru noi,
și vom începe să înțelegem lumea reală mijloace de punere în aplicare
programe bazate pe web și site-uri mai mult, în general,
și, de asemenea, foarte securitate implicațiile pe care le-am doar
a început să zgârie suprafața de.
Iată ce ne așteaptă în zilele următoare.
>> [VIDEO PLAYBACK]
>> -A Venit cu un mesaj, cu un protocol toată proprie.
El a venit la o lume de crudă firewall-uri, routere nepăsătoare,
și pericole mult mai rău decât moartea.
El este rapid.
E puternic.
E TCP / IP, și el are adresa ta.
"Warriors of net."
[END VIDEO PLAYBACK]
DAVID MALAN: primește săptămâna viitoare.
Ne veți vedea atunci.
[VIDEO PLAYBACK]
-Si Acum, "Gânduri profunde" de Daven Farnham.
-David Începe întotdeauna prelegeri cu "Bine".
De ce nu, "Aici e solutia la set problemă din această săptămână "
sau "Suntem oferindu voi toti o A?"
[Rîzînd]
[END VIDEO PLAYBACK]