[SCRÂȘIT] [FOSȘIT] [CLIC] JASON KU: Bună dimineața, tuturor. Ce mai face toată lumea? Weekend lung frumos din care tocmai am venit... Mă descurc bine. De fapt, sunt puțin răcit. Aw... da, din păcate. Dar după asta, nu mai am nimic săptămâna asta, așa că e bine. OK, deci data trecută, săptămâna trecută, am vorbit despre cum... ne-am uitat la problema de căutare despre care am vorbit la începutul săptămânii și am arătat că, într-un anumit model de calcul, am putut compara doar două obiecte pe care le-am stocarea în mine-- că stochez și obținem un număr constant de ieșiri pe ceea ce aș putea-- cum aș putea identifica aceste lucruri, cum ar fi egale, sau mai mici decât, sau ceva de genul acesta, apoi am desenat un arbore de decizie și am am obținut această legătură că, dacă aș avea n ieșiri, aș cere ca arborele meu de decizie să aibă cel puțin log n înălțime. Și astfel, în acest model, nu pot găsi lucrurile mai repede decât log n time. Dar, din fericire, ne aflăm într-un model de calcul care are o operație mai puternică - și anume, accesarea aleatorie. Și dacă am stocat lucrurile pe care le căutăm, avem chei unice, iar acele chei sunt numere întregi. Apoi, dacă am un articol cu ​​cheia K, dacă îl stochez la indexul K în matricea mea, atunci îl pot găsi și îl pot manipula în timp constant. E destul de misto. Așa am numit o matrice de acces direct. O matrice cu acces direct - într-adevăr nu este diferită de o matrice obișnuită, cu excepția faptului că cum o folosiți când vorbim despre secvențe este că dăm semantică extrinsecă sloturilor în care stocăm aceste lucruri. Practic, aș putea pune orice articol în orice slot. Acolo unde era în matricea mea nu avea nimic de-a face cu ceea ce erau acele lucruri. Aici impunem semantică intrinsecă matricei mele că, dacă am un element cu cheia K, trebuie să fie la indexul K. Acesta este lucrul de care profităm aici. Și apoi putem folosi această operațiune de acces aleatoriu cu ramificare liniară drăguță și puternică pentru a găsi acel lucru în timp constant, pentru că acesta este modelul nostru de calcul. OK, atunci care a fost problema cu această matrice cu acces direct? Oricine strigă. Spațiu... corect. Așa că a trebuit să instanțiem o matrice de acces direct care să fie de dimensiunea spațiului cheilor noastre. În general, locația mea de index este... ar putea merge de la 0 la un număr pozitiv. Dacă aș avea numere pozitive foarte mari , dacă aș sorta... dacă aș căuta printre ID-urile tale MIT, ar trebui să am o matrice de acces direct care să acopere acel spațiu de chei posibile pe care le-ai putea avea. Și asta ar putea fi mult mai mare decât n. Și în restul timpului am vorbit despre cum să remediam această problemă de spațiu. Putem reduce spațiul luând acel spațiu cheie mai mare de la 0 la u, care ar putea fi foarte mare, și să îl mapam într-un spațiu mic. Acum, în general, dacă vă ofer o funcție hash fixă ​​acolo, asta nu va fi bine în-- pentru toate intrările. Dacă intrările dvs. sunt foarte bine distribuite în spațiul cheie, atunci este bine, dar, în general, ar exista funcții hash cu unele intrări care vor fi proaste. Asta am argumentat noi. Și așa, pentru tot restul timpului acolo, am vorbit despre familiile hash, alegerea aleatorie a unei funcții hash dintr-un set mare de funcții hash, care avea o proprietate care, dacă aș alege acest lucru la întâmplare și tu, generând intrarea ta, nu ai fi făcut-o. Nu știu ce numere aleatoare am ales, așteptările față de alegerea mea aleatoare-- eu-- eu sunt cel care rulează algoritmul, nu tu îmi dai intrarea-- acea alegere aleatorie-- algoritmul meu se comportă foarte bine în așteptare. În special, am avut timp constant pentru găsirea, inserarea și ștergerea în această structură de date, în așteptare. Am făcut o mică dovadă a... că legăturile de lanț în care am stocat coliziunile în funcția noastră hash -- în tabelul nostru hash -- îmi pare rău - nu ar fi foarte lungi și, deci, dacă ar fi constante, atunci nu o fac. Nu trebuie să caut mai mult decât un număr constant de lucruri când merg într-o locație index cu hashing. Își amintește toată lumea despre ce am vorbit săptămâna trecută? Nu ți-am arătat această diagramă la sfârșit, dar ți-o arăt acum. În esență, ceea ce am avut a fost că avem o grămadă de moduri diferite de a face față acestei interfețe setate. Și săptămâna trecută, am vorbit despre matricea sortată, apoi am vorbit despre această matrice cu acces direct și acest tabel hash, care se descurcă mai bine pentru aceste dicționari - operațiile de căutare, inserare și ștergere - sau cel puțin mai bine într-un sens așteptat. Care este cea mai proastă performanță a unui tabel hash? Dacă trebuie să caut ceva într-un tabel hash și se întâmplă să aleg un tabel hash prost -- funcție hash, care este cel mai rău caz aici? Ce? n, nu? Este mai rău decât o matrice sortată, deoarece, potențial, am indexat tot ceea ce stocam la același index în tabelul meu hash și, pentru a putea distinge între ele, nu pot face nimic mai mult decât o căutare liniară. Aș putea stoca structura de date a altui set ca lanț și aș face mai bine așa. De fapt, așa face Java. Ei stochează o structură de date despre care vom vorbi săptămâna viitoare ca lanțuri, astfel încât să poată obține, în cel mai rău caz, log n. Dar, în general, tabelul hash este bun numai dacă permitem... OK, vreau să se aștepte bine, dar în cel mai rău caz, dacă chiar am nevoie ca operațiunea să fie în cel mai rău caz, chiar nu pot să permit vreodată timp liniar pentru o operațiune de acest fel, atunci nu vreau să folosesc un tabel hash. Și așa pe setul tău p 2, tot ceea ce îți cerem este cel mai rău caz, așa că probabil că nu vrei să folosești tabele hash. BINE? Da? PUBLIC: Ce înseamnă indicele e? JASON KU: Ce înseamnă indicele e? Grozav. În acest grafic, am pus un indice pe acesta este un timp de rulare așteptat, sau un A care înseamnă că acesta este un timp de rulare amortizat. La sfârșit, am vorbit despre cum, dacă am avea prea multe lucruri în tabelul nostru hash, atunci, atâta timp cât nu am făcut-o prea des, acesta este un argument mic, dar aceleași tipuri de idei ca și matricea dinamică -- dacă, ori de câte ori obținem un liniar -- suntem mai mult decât un factor liniar distanță de locul în care încercăm -- practic, factorul de umplere pe care încercam să fim, atunci am putea reconstrui complet tabelul hash cu noua funcție hash aleasă aleatoriu din tabelul nostru hash cu o dimensiune nouă și am putea obține limite amortizate. Și asta este ceea ce Python-- modul în care Python implementează dicționare, sau seturi, sau chiar obiecte atunci când încearcă să mapeze cheile la diferite lucruri. Deci sunt tabele hash. Grozav. Lucrul cheie aici este, ei bine, de fapt, dacă gama ta de taste este mică, sau dacă tu, ca programator, ai capacitatea de a alege cheile cu care identifici obiectele tale, poți alege de fapt acel interval să fie mic, să fie liniar, să fie mic în raport cu articolele dvs. Și nu aveți nevoie de o masă hash. Puteți utiliza doar o matrice cu acces direct, pentru că dacă știți că spațiul dvs. cheie este mic, este grozav. Deci o mulțime de programatori C probabil că ar dori să facă așa ceva, pentru că nu au acces la -- poate programatorii C++ ar avea acces la tabelul lor hash. Aveți întrebări despre chestia asta înainte să trecem mai departe? Da? PUBLIC: Deci de ce este [INAUDIBIL]? JASON KU: De ce este de așteptat? Când construiesc, aș putea insera... Inserez aceste lucruri de la x 1 câte 1 în tabelul meu hash. Fiecare dintre aceste operațiuni de inserare -- mă uit în sus pentru a vedea dacă asta -- un element cu acea cheie există deja în tabelul meu hash. Și așa că trebuie să mă uit în josul lanțului pentru a vedea unde este. Cu toate acestea, dacă se întâmplă să știu că toate cheile mele sunt unice în introducerea mea, toate elementele pe care încerc să le stochez sunt unice, atunci nu trebuie să fac această verificare și pot obține un timp liniar în cel mai rău caz. Are sens? În regulă. Este o subtilitate, dar asta e o întrebare grozavă. OK, așa că astăzi, în loc să vorbim despre căutare, vorbim despre sortare. Săptămâna trecută, am văzut câteva moduri de a face sortare. Unele dintre ele erau pătratice - sortarea prin inserție și sortarea selecției - și apoi am avut una care a fost n log n. Și chestia asta, n log n, părea destul de bună, dar pot să mă descurc mai bine? Pot să fac mai bine? Ei bine, ceea ce vom arăta la începutul acestei clase este, în acest model de comparație, nu. n log n este optim. Și vom trece prin aceeași linie de raționament pe care am avut-o săptămâna trecută. Deci, în modelul de comparație, ce am folosit când am încercat să argumentăm că orice algoritm de model de comparație va dura cel puțin log n timp? Ceea ce am făcut a fost că am spus, OK, mă pot gândi la orice model din modelul de comparație -- orice algoritm din modelul de comparație ca așa -- se întâmplă niște comparații. Se ramifică într-un sens binar, dar ai putea să o generalizezi la orice factor de ramificare constantă. Dar pentru scopurile noastre, binarul e bine. Și ceea ce am spus a fost că au existat cel puțin n ieșiri-- într- adevăr n plus 1, dar-- cel puțin comanda n ieșiri. Și am arătat că-- sau v-am argumentat că înălțimea acestui copac trebuie să fie de cel puțin log n-- log numărul de frunze. Trebuia să fie cel puțin log numărul de frunze. Aceasta a fost înălțimea arborelui de decizie. Și dacă acest arbore de decizie reprezenta un algoritm de căutare, trebuia să merg în jos și să efectuez aceste comparații în ordine, să ajung la o frunză unde aș scoate ceva. Dacă înălțimea minimă a oricărui arbore binar pe un număr liniar de frunze este log n, atunci orice algoritm din modelul de comparație trebuie să ia, de asemenea, log n timp, deoarece trebuie să facă atâtea comparații pentru a diferenția între toate rezultatele posibile. Are sens? În regulă. Deci, în problema de sortare, câte ieșiri posibile există? Care este rezultatul unui algoritm de sortare? PUBLIC: [INAUDIBIL] JASON KU: Ce? Care-i treaba? O listă-- în special, având în vedere contribuția mea-- un set de articole A care are dimensiunea n-- ceea ce vă voi da este o permutare a acelei liste. Deci, pentru fiecare index, să zicem, aș putea să vă spun unde merge. Un alt mod în care aș putea spune este, unde se duce primul articol , unde se duce al doilea articol , unde se duce al treilea element - bla, bla, bla -- așa. Deci câte opțiuni diferite de permutare există? Ei bine, câte opțiuni am pentru primul lucru despre unde ar putea fi în matricea sortată finală? Ar putea fi în oricare dintre locuri, deci este n. Ce zici de acesta, al doilea? Ei bine, nu poate merge acolo unde a mers acesta, corect, dar poate merge oriunde altundeva. Deci este n minus 1. Și deoarece acestea sunt alegeri independente pe care le fac, dacă le înmulțesc pe toate împreună, obțin 9 permutări factoriale care reprezintă numărul de ieșiri posibile pe care le am pentru algoritmul meu de sortare. Deci, pentru mine, pentru a avea o ieșire pentru algoritmul meu de sortare să fie corectă, am nevoie de cel puțin n frunze factoriale. Are sens? BINE. Lucrul frumos despre a face asta săptămâna trecută este că acesta este într-adevăr doar numărul de frunze și acesta este într-adevăr numărul de frunze. Deci, care este numărul de frunze este factorial theta. Aici este de fapt n factorial, dar o voi pune acolo. Și aici obținem un factorial n. Înțeleg. Deci este cel puțin omega n factorial. Asta te face mai fericit? Theta aici-- mulțumesc-- trebuie să fie cel puțin. Deci asta a fost corect. OK, deci cel puțin atât de mulți -- există algoritmi care, dacă ar fi -- ar putea dura două rute diferite pentru a ajunge la aceeași ieșire. Deci aceasta este o limită inferioară a numărului de frunze. BINE? Deci, ceea ce spune acest argument este că, dacă doar înlocuiesc numărul de frunze n aici cu n factorial, obțin acum o limită inferioară de sortare a comparației similare. Deci, ce este log de n factorial? Acest lucru este familiar de la p setul 1 poate. Deci un lucru pe care l-aș putea face este că aș putea introduce formula Sterling, nu? Și asta îmi va da ceva de forma n log n. Dar care este alt mod în care aș putea limita inferioară n factorial? Ei bine, am o grămadă de lucruri aici. Este n factorial. Jumătate dintre aceste lucruri-- aceste jumătate, n/2 lucruri-- sunt mai mari sau egale cu n/2. Asta are sens? Deci, cu siguranță pot limita mai jos acest lucru cu n/2 la n/2. Este ceva mai ușor de luat un buștean. Dacă luați un jurnal din asta, este asimptotic n log n. Deci, ceea ce obținem aici este că orice algoritm de sortare de aici necesită cel puțin n log n comparații, așa că o sortare de îmbinare este cel mai bun lucru pe care îl putem face. Asta are sens pentru toată lumea? Pur și simplu facem o analiză pe care am avut-o despre arborii de decizie, conectăm frunzele cu înălțimea minimă a oricărui arbore binar pe acel număr de frunze și doar înlocuim n cu n factorial - nimic foarte interesant aici. Da? PUBLIC: [INAUDIBIL] n peste 2. JASON KU: Da, sigur. Puteți să introduceți formula Sterling, dar am făcut asta, așa că aș putea la fel de bine să clarific. Există n termeni aici în produs. Jumătate dintre ele sunt cel puțin n/2. Are sens? Pot limita mai jos acest produs cu ceva mai mic de jumătate din termeni -- un produs din asta, și asta va fi bine. Deci iau n/2 dintre ele și înmulțesc n/2 în total, de n/2 ori. Are sens? Oferă doar o limită inferioară. Am nevoie doar de ceva mai mic decât toți acești termeni. Și înmulțiți-le pe toate împreună, și asta îmi va da o limită inferioară. OK, deci nu putem face mai bine decât n log n în modelul de comparație, dar ceea ce am făcut săptămâna trecută a fost să folosim accesul aleatoriu și o matrice de acces direct pentru a face mai bine. BINE? Se poate gândi cineva cum să folosească această idee pentru a sorta mai repede? Și o să vă fac o avertizare aici. Vă voi lăsa să presupuneți că cheile lucrurilor pe care încercați să le rezolvați sunt unice. Și să spunem că sunt într-o limită... într-un interval mic. Deci, cum aș putea folosi o matrice cu acces direct pentru a sorta mai rapid? Vreo idee? Da? PUBLIC: Ați putea să introduceți literalmente [INAUDIBLE] într- o matrice de acces direct? JASON KU: Uh-huh. PUBLIC: Și apoi te uiți la acea matrice și cum să o sortezi. JASON KU: OK. Deci ceea ce spune colegul tău este exact corect. Este ceva ce îmi place să-l numesc sortare matrice cu acces direct. Nu o vom numi așa, pentru că este ceva mai general despre care vom vorbi într-o secundă. Dar ceea ce spunea colegul tău este, instanțiați o matrice mare cu acces direct - sortarea matricei cu acces direct. Instanțiez această matrice mare de acces direct la spațiul cheilor mele și ceea ce spunea colegul tău a fost că iau fiecare dintre elementele din... lucrurile pe care încerc să le sortez, mă uit la fiecare dintre cheile lor și îl înfig în accesoriul direct exact acolo unde trebuie , în timp constant. Grozav. Acum, ți-am dat acest avertisment că toate cheile erau unice, așa că nu trebuie să mă ocup de coliziuni aici. Dar apoi, după ce am terminat cu asta, toate aceste lucruri sunt acum în ordine, iar ceea ce pot face este să merg în jos pe această listă. Multe dintre aceste celule sunt, posibil, goale. Unele dintre chei s-ar putea să nu fie acolo, dar ceea ce pot face este să parcurg această listă, să scot fiecare articol care există, să le pun într-o matrice... Am terminat. Bagă o cheie aici și apoi... bine. Faceți o matrice de acces direct. Stocați articole-- elementul x din index x.key. Mergeți în matricea de acces direct și returnați articolele văzute în ordine. Are sens pentru toată lumea? Bine, cât durează acest pas? Construirea unei matrice de acces direct ordine u-- OK, deci aceasta este ordinea u-- cât timp durează? Câte articole trebuie să introduci? Comandați n, sau doar n-- și cât timp durează să inserez fiecare dintre aceste lucruri în matricea mea de acces direct? Cel mai rău caz constant de timp - deci acesta este de n ori cel mai rău caz constant de timp - grozav. Cât durează acesta din urmă? Oricine? O dintre voi, de asemenea, corect, pentru că merg pe toată lungimea dumneavoastră. Deci, acest algoritm ia, în total, n plus u timp. Asta e super. u este mai mare decât n, deoarece am presupus chei distincte. Dar dacă u este de ordinul lui n, atunci avem acum algoritmul de sortare liniară în timp. Da? Care-i treaba? PUBLIC: [INAUDIBIL] JASON KU: Îmi pare rău. Trebuie să vorbești. PUBLIC: Cum atașați cheile la [INAUDIBLE]? JASON KU: Cum atașez cheile la intrările mele în... pentru o structură de date setată despre care am tot vorbit, toate articolele mele au chei. Este doar ceva pe care îl impunem asupra aportului nostru. PUBLIC: [INAUDIBIL] JASON KU: Fiecare dintre taste este... în acest caz, trebuie să fie un număr. Este un punct frumos. Facem acest lucru pentru a vorbi despre sortarea elementelor în general, astfel încât să nu avem de a face cu potențial dacă aceste chei au valori asociate cu-- sau alte lucruri asociate-- le punem pe acel articol și vor fi în continuare acolo. Dar, în general, dacă doriți doar să sortați numere întregi, ați putea spune că .key este -- indică înapoi la obiectul în sine, dacă doriți să sortați doar câteva numere întregi. Are sens? Este o întrebare bună, totuși. OK, deci asta ne oferă un algoritm de timp liniar când u este mic și, în această condiție, am chei unice când vreau să sortez. Acestea sunt destul de restrictive, așa că ar putea dori să generalizăm puțin acest lucru. BINE? Deci, acesta este sortarea matricei cu acces direct. Dacă am avea un set de chei puțin mai mare? Deci, să presupunem că u este theta n implică sortarea liniară în timp. Grozav. Deci, acum, ce se întâmplă dacă extindem puțin intervalul? Să spunem că u este mai mic sau egal cu n pătrat -- poate doar mai mic decât. OK, acesta este un interval mai mare Și dacă am instanția o matrice cu acces direct de dimensiunea pătratică, am avea un algoritm de timp pătratic. Acest lucru nu este de ajutor. Are cineva o modalitate prin care am putea sorta numerele întregi care sunt între 0 și n pătrat? Poate folosind lucrurile pe care le aveam mai sus... Da? PUBLIC: [INAUDIBIL] sortați după primul n, cam ca prima cifră. JASON KU: Colegul tău spune exact ceea ce caut eu , ceea ce este grozav, adică poate am putea împărți acest număr mai mare în două numere mai mici. Orice număr întreg care este între 0 n pătrat poate fi scris ca: cheia poate fi unele a și b, unde a este în esență n mai mare și b este n mai mic. Asta e cam ciudat. OK, deci ce vreau să spun de fapt prin asta? Adică să lăsăm a fi K, când îl împart la n-- întreg, etajul-- întreg cheie pentru a împărți la n. Și b este egal cu K mod n. Deci acesta este un număr care este mai mic decât n și acesta este un număr care este mai mic decât n. Are sens? Și de fapt, pot recupera K în orice moment spunând că K este egal cu un plus b. În esență, l-am descompus într-o reprezentare de bază n a acestui număr. Și am două cifre în acel număr. Aceasta este cifra a n-a-- n și aceasta este cifra celor. Are sens? Bine, deci acum să presupunem că am această listă de numere-- 17, 3, 24, 22, 12. Aici am cinci numere. Deci, ce este n în acest caz? 5-- OK, nu atât de interesant. n este 5 aici. Și voi reprezenta acest lucru ca cinci perechi de numere care sunt fiecare în limitele de la 0 la 4. Are sens? Deci, care este reprezentarea mea a, b a lui 17? 3, 2-- OK. Da, deci sunt de 3 ori 5 plus 2. E bine. Adică 17. Da? Cred că colegul tău a făcut asta, nu? Am toate astea notate, așa că am de gând să le scriu. Și sper că am făcut-o corect. OK-- 3, 2; 0, 3; 4, 4; 4, 2; 2, 2-- OK. Deci acum am o grămadă de lucruri pe care vreau să le sortez în funcție de această funcție pe care o am. Acestea nu mai sunt doar numere întregi pe care trebuie să le sortez. Trebuie să sortez după transformarea acestui lucru într-un număr. Are sens? Deci, oricine are idei despre cum am putea-- apropo, acestea sunt ambele operațiuni în timp constant pe computer, atâta timp cât este o diviziune întreagă și acesta este mod. Python are, de asemenea, un lucru frumos, cred, în operațiunile sale standard, care este divmod of K, n. Este corect? Da. Deci, dacă vrei să folosești asta, poți. OK, deci cum sortăm aceste tupluri? Acestea sunt tupluri, nu? Sunteți sigur că sunteți foarte familiarizați cu tuplurile până acum. Cum sortez aceste tupluri? Care este cea mai importantă cifră din chestia asta? Dacă ar trebui să sortez una dintre cifre și să obțin ceva care este aproape de sortat, ce este mai important - cifra lui 1 sau cifra lui n? OK, avem o discrepanță aici. Cine spune 1? Cine spune n? Cineva care a spus n spune-mi de ce. Oh, toți gândiți așa fără niciun motiv. PUBLIC: [INAUDIBIL] JASON KU: Da. Îmi pare rău. Acest lucru este puțin confuz. Aceasta este cifra lui 1. Aceasta este cifra lui n. Aceasta este cifra lui n. Aceasta este cifra 1 în modul în care scriu asta. Are sens? Da? PUBLIC: [INAUDIBLE] are o cifră diferită în interiorul acestuia. Așa că ai putea avea [INAUDIBIL], dar asta îți spune doar unde se află în ceea ce privește categoria n specifică în care se află. Deci este mai mult un [INAUDIBIL]. JASON KU: Da. Deci ceea ce spune colegul tău este exact corect. Aș putea varia b tot ce vreau, cu același a. Dacă schimb a cu 1, nu contează ce este b-- va fi mai mare. Are sens? K este mult mai sensibil la a decât la b, deci a este mai important decât b. Are sens? Așa că, dacă aș vrea doar să obțin un algoritm de timp liniar, aș putea pur și simplu să sorteze după cifrele lor mai mari și să sper că nu diferă foarte mult în ceea ce privește lucrurile mai mici. Am cam aranjat aceste lucruri. Are sens? BINE. Dacă chiar vreau să sortez aceste lucruri? Ceva indicii? Da? Trebuie să le sortez pe ambele, într-un anumit sens. Ceea ce o să vă spun acum este un algoritm pe care îmi place să-l numesc sortare tuple, dar vă puteți gândi și la sortarea foilor de calcul Excel. Am o foaie de calcul Excel cu o grămadă de date. Am o prioritizare cu privire la cât de importante sunt cheile pentru mine... coloanele. Și dacă am o coloană foarte importantă și o ordine a coloanelor despre cât de importante sunt pentru mine, pot căuta în mod repetat coloanele până când sunt sortate în funcție de preferințele mele. Este ceva ce poate ai făcut. Acum, dacă am o ordonare pe preferințele coloanelor mele, încep prin a le sorta pe toate pe cel mai important sau pe cel mai puțin important lucru? Ce? Cine spune cel mai mult? Cine zice cel putin? Există o discrepanță aici. Bine, hai să încercăm. În regulă, sortarea tuplelor... să începem prin a sorta aceste lucruri mai întâi după cel puțin semnificativ și apoi... nu, mai întâi cel mai semnificativ și apoi cel mai puțin semnificativ. Acesta a fost primul lucru pe care te-am întrebat, nu? Bine, deci acestea sunt cele mai importante lucruri, primele. Și acestea sunt lucrurile mai puțin semnificative. Bine, în loc să- l scriu ca tupluri, le voi scrie ca 32, 03, 44, 42, 22. Toată lumea e bine? Aceasta este doar reprezentarea de bază cinci. Bine, deci să începem prin a sorta toate aceste lucruri după cel mai important lucru, care este de tipul ăsta, tipul ăsta, tipul ăsta, tipul ăsta și tipul ăsta. Deci, cum o fac? Primul este 03, al doilea este 22, următorul este 32, 42 și apoi 44 - poate 44? Nu știu. Contează, ordinea în care pun aceste lucruri? Nu știu. O să-l păstrez pentru moment în aceeași ordine. În regulă, așa că l-am sortat după cel mai puțin semnificativ-- sau cel mai semnificativ-- scuze-- termenul principal. Și acum voi sorta după cele mai puțin semnificative. Deci, care este cel mai puțin semnificativ aici? 22-- atunci 2 este, de asemenea, acesta este, de asemenea, 2. Acesta este, de asemenea, 2. Acesta este 3. Și listă sortată-- voila. De ce nu a funcționat? Da? PUBLIC: [INAUDIBIL] JASON KU: Da. Deci, ceea ce s-a întâmplat este că am ținut cont de sortarea cifrelor semnificative, dar când am făcut lucrul mai puțin semnificativ , mi-a șters toată munca de aici. Are sens? În cazul legăturilor, vrem ca lucrul mai semnificativ să aibă prioritate, așa că vrem să facem acel lucru în ultimul rând. Are sens? Deci modalitatea corectă de a face asta-- acesta este cel mai important primul [INAUDIBIL] nu este bun. Bine, cel puțin semnificativ mai întâi... hai să încercăm asta. Deci cel mai puțin semnificativ aici este 2. OK, așa că văd 32, 42, 22, 03 și apoi 44. OK? Suna bine? Cel mai puțin semnificativ mai întâi-- acum o fac cel mai important. Ordonez cel mai semnificativ lucru. OK, deci care este cel mai important lucru? 03, 22, 32-- cele mai semnificative patru-- 44 și 42-- cool. Suntem aranjați, nu? Am făcut ce mi-ai spus să fac. Am sortat după cel mai semnificativ lucru. Care este problema aici? Ce am făcut greșit? Ai vrut să pun 42 aici și 44 aici, nu? Pentru că 42 au fost primul la intrare și 44 au venit pe al doilea, nu? OK, dacă un algoritm de sortare menține această proprietate că, dacă sunt același lucru, atunci ieșirea își menține ordinea de la intrare la ieșire - ordinea lor relativă - asta este ceea ce numim un algoritm de sortare stabil . Și așadar, dacă avem un algoritm de sortare stabil atunci când facem sortare tuple, atunci când sortăm pe diferite chei sau coloane ale unui set, vrem cu adevărat să folosim un algoritm de sortare stabil. Are sens? Pentru că altfel, s- ar putea să încurcăm munca pe care am făcut-o înainte într-un fel anterior de lucruri mai puțin semnificative. Și deci da, vrem aici un algoritm de sortare stabil, pentru că atunci vom ajunge să ne sortăm treaba. Are sens? Da? PUBLIC: [INAUDIBIL] JASON KU: Deci, ceea ce spune colegul tău - hai să sortăm după cele mai semnificative, apoi să ne uităm la toate lucrurile cu unul dintre acelea care sunt la fel și acum sortăm asta. Asta e ceva ce am putea face. Cât timp ar dura asta? Ei bine, să presupunem că nu am folosit jumătate din setul meu mai semnificativ de cifre. Să spunem că folosesc doar n/2 sau... că nu o să obțin ceea ce vreau. PUBLIC: [INAUDIBIL] JASON KU: Spune din nou. PUBLIC: Vom lua n pătrat [INAUDIBIL].. JASON KU: Da. Deci, ce vom face, dacă avem acces direct sortarea matricei -- dacă apoi intru în fiecare dintre aceste cifre și încerc să sortez lucrurile care sunt acolo, asta va dura timp. Va dura timp pentru fiecare dintre aceste cifre. S- ar putea să existe o mulțime de ciocniri într-unul dintre lucruri, așa că s-ar putea să îmi ia mai mult timp pentru a sorta asta decât liniar. Are sens? Așa că aș prefera să fac acest tip de comportament de tip tuplu, sortând lucrurile mai mici, sortând lucrurile mai mari. Și pentru că am doar un număr constant de lucruri în tuplurile mele, acest lucru este important, pentru că am doar două lucruri care mă îngrijorează aici. Trebuie doar să fac două treceri ale unui algoritm de sortare pentru a putea sorta aceste numere. Totuși, pot folosi sortarea matricei cu acces direct aici? Care a fost stipulația inițială pe care am avut-o cu privire la matricea de acces direct? Că cheile erau unice... este exact opusul a ceea ce avem aici. Avem lucruri care ar putea fi la fel. Așa că renunțăm... nu o putem face. Ce facem in schimb? Da? PUBLIC: [INAUDIBIL] JASON KU: Ai spus deja lucrul pe care îl caut, așa că e grozav. Colegul tău a spus, de ce nu putem pune mai multe lucruri la cheie? De ce nu putem pune o listă acolo? Exact asta facem. Aceasta se numește sortare de numărare. Și ceea ce facem aici este că încă mai avem această matrice cu acces direct de spațiu u minus 0 la u minus 1, dar în loc să stocăm un lucru aici la fiecare tastă K, stocăm un pointer către un lanț. Sună a hashing, nu? Dar important este că trebuie să mă asigur, pe măsură ce introduc lucruri aici, că mențin ordinea în care au intrat. aici sus pe care le aveam înainte. Așa că am nevoie de ceea ce aș spune este o structură a secvenței de date , ceva care va menține ordinea în care eu-- ordinea extrinsecă pe care o aveam atunci când pun aceste lucruri. Deci, deoarece am mai multe lucruri cu K, voi merge să le pună în ordine. Pot pune-- am un pointer către o matrice dinamică sau o listă legată, unde adaug doar lucruri la sfârșit. Și apoi, la sfârșitul algoritmului meu, când citesc lucrurile, pot doar să mă uit la oricine care are o structură de date nevide aici și să le citesc în ordinea în care au venit. Are sens? Deci, pentru acest exemplu, voi face acest ultim pas aici de la primul rând la al doilea rând. Voi avea această matrice de acces direct cu 0, 1, 2, 3, 4 pe sloturi. Deci, cum voi face acum acest tip de numărare? Am 32, 42, 22, 03 și 44. Pot să-l iau pe primul, 32. Sort după cel mai important lucru. Îl lipesc aici-- 32, și apoi 44-- 42-- Îmi pare rău-- 42, 22. Acesta nu este atât de diferit decat matrice dinamică - sortare matrice cu acces direct. Dar când ajungem la acest duplicat, 44 aici, acum avem două lucruri în acest lucru. Și pentru că le menținem în ordine în această secvență, le anexez la sfârșit. Apoi, când merg și citesc diferitele lucruri, atunci le returnez într-un mod stabil, așa cum vreau să fie. Are sens? Și nu suprascrie munca pe care am făcut-o pe cifrele semnificative inferioare. Deci, cât durează asta? De asemenea, aceasta ia doar ordinea n plus u, pentru că instanțiez acest lucru de mărimea u. Și apoi, cât de mari sunt aceste structuri de date? Ei bine, poate stochez unul, o sumă constantă pentru fiecare index. Deci asta este un u peste cap. Și apoi plătesc 1 pentru fiecare articol pe care îl depozitez. Aceste lucruri sunt doar lungimile. Suma totală a lungimilor lor este n, deoarece stochez doar n lucruri acolo. Deci, cantitatea totală de spațiu, cantitatea totală de muncă pe care trebuie să-l fac este comandă-- trebuie să pot petrece în timp constant și trebuie să pot parcurge aceste lucruri, să repet peste ele în timp liniar. Dar dacă am asta, primesc n plus u. Da? PUBLIC: Cum vă asigurați că, în lista dvs. conectată sau dinamica -- acele elemente, cum ar fi patru egal cu patru -- cum vă asigurați că acestea sunt sortate? JASON KU: Deci colegul tău spune, cum mă asigur că lucrurile din aceste liste, unde se ciocnesc, cum te asigur că sunt sortate? Eu nu. Mă asigur doar că au venit în ordinea în care au venit. Dar atâta timp cât am sortat corect cifrele de ordine inferioară în lucrurile anterioare, presupun că ordinea lor pe măsură ce intră va fi sortată, dacă se ciocnesc. Asta e presupunerea. Acesta este motivul pentru care le fac de la cele mai puțin semnificative la cele mai semnificative este ca să știu că, atunci când se ciocnesc, lucrurile de bază sunt deja sortate în intrare. Are sens? Grozav... da? PUBLIC: Deci această matrice nu este la fel de mare ca tine. Este la fel de mare ca n. JASON KU: Folosesc o matrice de acces direct pe taste... oh, acesta este n. Deci numărarea sortării este generală pentru orice u. Tocmai mi s-a întâmplat să te aleg că ești n în acest caz când am împărțit chestia asta în n pătrat. Dar acest concept general este... nu contează ce aleg pentru tine. Are sens? BINE. Dar îl vom folosi chiar acum pentru a sorta intervale mai mari de numere. Exact asta a fost ideea. Vom combina sortarea tuplelor, vom folosi sortarea de numărare ca sortare auxiliară - algoritm de sortare stabil pentru a-și face toată munca pe aceste cifre. Și astfel, pentru a sorta n numere de dimensiune pătrată, obțin timpul liniar, ceea ce este grozav, deoarece u este n în acest caz. Dar pot extinde asta? Și dacă aș fi cubit? Ce se întâmplă dacă aș avea până la dimensiunea u egală cu n cuburi sau mai puțin de n cuburi? Câte cifre aș avea acolo? De câte dimensiuni n cifre am nevoie pentru a reprezenta un număr de dimensiune n cub? Vreo idee? Ce am făcut aici? Am împărțit un n. L-am luat și l-am depozitat. Ne-a rămas ceva de mărimea n. Dacă aș avea un număr de mărimea n cuburi, aș putea împărți un n. Am rămas cu ceva de n pătrat. Nu știu cum să mă descurc cu ceva de n pătrat. De fapt, da. Îl pot împărți în două numere de dimensiune n. Deci, dacă aș avea numere legate -- mărginite de sus de un cubic -- n cub -- aș putea să le împart în trei cifre. Trei este încă constantă. Și astfel l-aș putea împărți în trei cifre, le-aș putea sorta în funcție de prioritate crescătoare și le-aș sorta. Din nou, fac lucru liniar pe cifră. Am un număr constant de cifre, așa că obțin un algoritm de timp liniar. Da? PUBLIC: Când vine vorba de sortare [INAUDIBIL]---- JASON KU: Uh-huh. PUBLIC: Vă asigurați că timpul de rulare este, de asemenea, mare O din n plus u? JASON KU: Da. Deci, va fi întotdeauna O mare de n plus u, dar pentru că îmi limitez dimensiunea cifrei la n, u este n acolo și, prin urmare, obțin timp liniar. Are sens? Da. Deci ideea aici... asta este ceea ce numim sortare radix. Sortare Radix -- descompune numerele întregi, dimensiunea maximă u, într-o bază și un tuplu. Deci, practic, fiecare dintre cifrele mele poate varia de la 0 la n. Câte cifre de bază n fac dacă am un număr de mărimea u? Da, log n din u-- numărul de cifre este log n din u-- log-baza n din u. Și apoi sortați tuple pe cifre folosind sortarea de numărare, de la cel mai mic la cel mai semnificativ -- acesta este algoritmul. Cât durează asta? Cât timp durează sortarea pe o cifră care cuprinde cheia de la 0 la n? Timp liniar, nu? Comandă n timp - de câte ori trebuie să fac această sortare a tuplurilor? Numărul de cifre ori, nu? Deci, timpul de rulare al acestui algoritm-- mai întâi, trebuie să fac aceste lucruri, să rup fiecare dintre numerele întregi. Asta durează de n timp - de n ori numărul de cifre. A trebuit să creez fiecare dintre aceste tupluri -- deci n plus n ori numărul de cifre -- baza logică n din u. Așa că aici a trebuit să parcurg toate lucrurile. Și apoi aici, pentru fiecare lucru, l-am împărțit în jurnal de bază n de u cifre și atât a durat primul lucru. Și apoi, cât timp mi-a luat să sortez tuple? n timp pe cifră - așa că primesc și acest factor. Are sens? Cât durează asta? Este atât de bună? E rău? Pentru ce valori ale lui u este acest timp liniar? Dacă u este mai mic decât n față de c pentru o constantă c, atunci c iese din logaritm, log n al lui n este 1 și obținem un algoritm de timp liniar. Are sens? BINE. Deci, așa putem sorta în timp liniar, dacă lucrurile noastre sunt doar polinomial mari. Deci, la numărarea sortării, obținem n plus u. În sortarea radix, obținem, de asemenea, un algoritm de sortare stabil în care timpul de rulare este de n plus de n ori baza logică n din u. Are sens? Și apoi, în situațiile în care-- există o greșeală de tipar acolo în sortarea numărării-- asta ar trebui să fie atunci când u este de ordinul n-- numărarea curselor scurte în timp liniar. Și este timpul liniar și în cazul sortării de rating, dacă lucrurile noastre sunt mărginite de un polinom în n, de n la c pentru o constantă c. Are sens? În regulă, așa se sortează în timp liniar, cu avertismentul că numerele tale nu sunt prea mari. OK, ne vedem săptămâna viitoare.